{"raw_statement":[{"iden":"statement","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 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.\n\n<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."},{"iden":"input","content":"The first line contains integer _n_ (1  ≤  _n_  ≤  5·105) — the number of vertices in the tree.\n\n(_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."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input\n\n4\n1 s\n2 a\n3 s\n\nOutput\n\n3 1 1 0 \n\nInput\n\n5\n1 a\n2 h\n1 a\n4 h\n\nOutput\n\n4 1 0 1 0"}],"translated_statement":"[{\"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 \"}]\"","sample_group":[],"show_order":[],"formal_statement":"**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 \\in \\Sigma $, where $ \\Sigma = \\{a, b, \\dots, v\\} $ (22 lowercase English letters).  \nFor any simple path $ P $ in $ T $, let $ s(P) $ denote the string formed by concatenating the edge labels along $ P $.  \nA string $ s $ is *Dokhtar-kosh* if it can be rearranged into a palindrome, i.e., at most one character has odd frequency.\n\nFor each vertex $ v \\in V $, let $ \\mathcal{P}_v $ denote the set of all simple paths contained in the subtree rooted at $ v $.\n\n**Constraints**  \n1. $ 1 \\le n \\le 5 \\cdot 10^5 $  \n2. For each edge $ (p_{i+1}, i+1) $: $ 1 \\le p_{i+1} \\le i $, and the label $ c_{i+1} \\in \\Sigma $  \n\n**Objective**  \nFor each vertex $ v \\in \\{1, 2, \\dots, n\\} $, compute:  \n$$\nf(v) = \\max \\left\\{ |P| \\mid P \\in \\mathcal{P}_v \\text{ and } s(P) \\text{ is Dokhtar-kosh} \\right\\}\n$$  \nwhere $ |P| $ denotes the number of edges in path $ P $.","simple_statement":null,"has_page_source":false}