{"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 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\nHe 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.\n\nThe 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 pi and a letter ci (1  ≤  pi  <  i, ci is lowercase English letter), that mean that there is an edge between nodes pi and i and there is a letter ci written on this edge.\n\nPrint 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.\n\n"},{"iden":"input","content":"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 pi and a letter ci (1  ≤  pi  <  i, ci is lowercase English letter), that mean that there is an edge between nodes pi and i and there is a letter ci 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":"Input41 s2 a3 sOutput3 1 1 0 Input51 a2 z1 a4 zOutput4 1 0 1 0 "}],"translated_statement":null,"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 $ (p_i, i) $ for $ i = 2, \\dots, n $ is labeled with a character $ c_i \\in \\Sigma $, where $ \\Sigma $ is the set of lowercase English letters.  \nFor any path $ P $ in $ T $, let $ s(P) $ denote the string formed by concatenating the edge labels along $ P $.  \n\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 $ T_v $ denote the subtree rooted at $ v $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 5 \\cdot 10^5 $  \n2. For each $ i \\in \\{2, \\dots, n\\} $: $ 1 \\le p_i < i $, $ c_i \\in \\{a, b, \\dots, z\\} $  \n\n**Objective**  \nFor each vertex $ v \\in \\{1, \\dots, n\\} $, compute:  \n$$\nf(v) = \\max \\{ |P| \\mid P \\text{ is a simple path in } T_v \\text{ and } s(P) \\text{ is Dokhtar-kosh} \\}\n$$  \nOutput $ f(1), f(2), \\dots, f(n) $.","simple_statement":"Given a tree with n nodes rooted at 1, each edge has a lowercase letter. For each node v, find the longest path in its subtree such that the string formed by edge letters on the path can be rearranged into a palindrome.","has_page_source":false}