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

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.

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.

以防有人遗漏：在Arpa的土地上，我们拥有非常出色的女孩们。

Arpa 有一棵有根树（即连通无环图），包含 $n$ 个顶点。顶点编号为 $1$ 到 $n$，其中顶点 $1$ 是根节点。该树的每条边上都写有一个字母。Mehrdad 是 Dokhtar-kosh 风格事物的爱好者。他将一个字符串称为 Dokhtar-kosh，当且仅当该字符串的字符可以重排后构成回文串。

他向 Arpa 提出如下问题：对每个顶点 $v$，其子树中能构成 Dokhtar-kosh 字符串的最长简单路径的长度是多少？

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.

第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$）—— 树中顶点的数量。

接下来有 $(n - 1)$ 行，其中第 $i$ 行包含一个整数 $p_{i+1}$ 和一个字母 $c_{i+1}$（$1 \leq p_{i+1} \leq i$，$c_{i+1}$ 为小写英文字母，且在 a 到 v 之间，含端点），表示节点 $p_{i+1}$ 与节点 $i+1$ 之间存在一条边，且该边上写着字母 $c_{i+1}$。

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.

输出 $n$ 个整数。其中第 $i$ 个整数应为以第 $i$ 个顶点为根的子树中，构成 Dokhtar-kosh 字符串的最长简单路径的长度。