{"problem":{"name":"D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths(Hard)","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 vertex 1 is the root. There is a letter writt","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10118D"},"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 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## Input\n\nThe 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.\n\n## Output\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[samples]","is_translate":false,"language":"English"},{"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 $ (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) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10118D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}