D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

Codeforces

IDCF741D

Time3000ms

Memory256MB

Difficulty—

data structuresdfs and similartrees

English · Original

Chinese · Translation

Formal · Original

_Just in case somebody missed it: we have wonderful girls in Arpa’s land._ Arpa has a rooted tree (connected acyclic graph) consisting of _n_ vertices. The vertices are numbered 1 through _n_, the vertex 1 is the root. There is a letter written on each edge of this tree. Mehrdad is a fan of _Dokhtar-kosh_ things. He call a string Dokhtar-kosh, if we can shuffle the characters in string such that it becomes palindrome. <center>![image](https://espresso.codeforces.com/a7c274b610a81b8f39b3c667a30d97554c35d2f9.png)</center>He asks Arpa, for each vertex _v_, what is the length of the longest simple path in subtree of _v_ that form a Dokhtar-kosh string. ## Input The first line contains integer _n_ (1 ≤ _n_ ≤ 5·105) — the number of vertices in the tree. (_n_ - 1) lines follow, the _i_\-th of them contain an integer _p__i_ + 1 and a letter _c__i_ + 1 (1 ≤ _p__i_ + 1 ≤ _i_, _c__i_ + 1 is lowercase English letter, between _a_ and _v_, inclusively), that mean that there is an edge between nodes _p__i_ + 1 and _i_ + 1 and there is a letter _c__i_ + 1 written on this edge. ## Output Print _n_ integers. The _i_\-th of them should be the length of the longest simple path in subtree of the _i_\-th vertex that form a Dokhtar-kosh string. [samples]

[{"iden":"statement","content":"_Just in case somebody missed it: we have wonderful girls in Arpa’s land._\n\nArpa 有一棵有根树（连通无环图），包含 #cf_span[n] 个顶点。顶点编号为 #cf_span[1] 到 #cf_span[n]，其中顶点 #cf_span[1] 为根。树的每条边上都写有一个字母。Mehrdad 是 _Dokhtar-kosh_ 事物的爱好者，他称一个字符串为 Dokhtar-kosh，当且仅当我们可以重新排列该字符串中的字符，使其变为回文串。\n\n他询问 Arpa：对于每个顶点 #cf_span[v]，其子树中最长的简单路径所形成的字符串，其长度是多少，且该字符串为 Dokhtar-kosh 字符串。\n\n第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5·105]）——树中顶点的数量。\n\n接下来 #cf_span[(n - 1)] 行，第 #cf_span[i] 行包含一个整数 #cf_span[pi + 1] 和一个字母 #cf_span[ci + 1]（#cf_span[1 ≤ pi + 1 ≤ i]，#cf_span[ci + 1] 为小写英文字母，介于 _a_ 和 _v_ 之间，包含两端），表示节点 #cf_span[pi + 1] 与 #cf_span[i + 1] 之间有一条边，且该边上写有字母 #cf_span[ci + 1]。\n\n请输出 #cf_span[n] 个整数。第 #cf_span[i] 个整数应为以第 #cf_span[i] 个顶点为根的子树中，能形成 Dokhtar-kosh 字符串的最长简单路径的长度。"},{"iden":"input","content":"第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5·105]）——树中顶点的数量。#cf_span[(n - 1)] 行 follow，第 #cf_span[i] 行包含一个整数 #cf_span[pi + 1] 和一个字母 #cf_span[ci + 1]（#cf_span[1 ≤ pi + 1 ≤ i]，#cf_span[ci + 1] 为小写英文字母，介于 _a_ 和 _v_ 之间，包含两端），表示节点 #cf_span[pi + 1] 与 #cf_span[i + 1] 之间有一条边，且该边上写有字母 #cf_span[ci + 1]。"},{"iden":"output","content":"请输出 #cf_span[n] 个整数。第 #cf_span[i] 个整数应为以第 #cf_span[i] 个顶点为根的子树中，能形成 Dokhtar-kosh 字符串的最长简单路径的长度。"},{"iden":"examples","content":"输入\n4\n1 s\n2 a\n3 s\n输出\n3 1 1 0 \n\n输入\n5\n1 a\n2 h\n1 a\n4 h\n输出\n4 1 0 1 0 "}]"

**Definitions** Let $ T = (V, E) $ be a rooted tree with $ n $ vertices, where $ V = \{1, 2, \dots, n\} $ and vertex $ 1 $ is the root. Each edge $ (u, v) \in E $ is labeled with a character $ c \in \Sigma $, where $ \Sigma = \{a, b, \dots, v\} $ (22 lowercase English letters). For any simple path $ P $ in $ T $, let $ s(P) $ denote the string formed by concatenating the edge labels along $ P $. A string $ s $ is *Dokhtar-kosh* if it can be rearranged into a palindrome, i.e., at most one character has odd frequency. For each vertex $ v \in V $, let $ \mathcal{P}_v $ denote the set of all simple paths contained in the subtree rooted at $ v $. **Constraints** 1. $ 1 \le n \le 5 \cdot 10^5 $ 2. For each edge $ (p_{i+1}, i+1) $: $ 1 \le p_{i+1} \le i $, and the label $ c_{i+1} \in \Sigma $ **Objective** For each vertex $ v \in \{1, 2, \dots, n\} $, compute: $$ f(v) = \max \left\{ |P| \mid P \in \mathcal{P}_v \text{ and } s(P) \text{ is Dokhtar-kosh} \right\} $$ where $ |P| $ denotes the number of edges in path $ P $.

Samples

Input #1

4
1 s
2 a
3 s

Output #1

3 1 1 0

Input #2

5
1 a
2 h
1 a
4 h

Output #2

4 1 0 1 0

API Response (JSON)

{
  "problem": {
    "name": "D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths",
    "description": {
      "content": "_Just in case somebody missed it: we have wonderful girls in Arpa’s land._ Arpa has a rooted tree (connected acyclic graph) consisting of _n_ vertices. The vertices are numbered 1 through _n_, the ve",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF741D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_Just in case somebody missed it: we have wonderful girls in Arpa’s land._\n\nArpa has a rooted tree (connected acyclic graph) consisting of _n_ vertices. The vertices are numbered 1 through _n_, the ve...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"_Just in case somebody missed it: we have wonderful girls in Arpa’s land._\\n\\nArpa 有一棵有根树（连通无环图），包含 #cf_span[n] 个顶点。顶点编号为 #cf_span[1] 到 #cf_span[n]，其中顶点 #cf_span[1] 为根。...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a rooted tree with $ n $ vertices, where $ V = \\{1, 2, \\dots, n\\} $ and vertex $ 1 $ is the root.  \nEach edge $ (u, v) \\in E $ is labeled with a character $ c \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments