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

题意翻译

一棵根为 $1$ 的树,每条边上有一个字符(`a` 到 `v` 共 $22$ 种)。一条简单路径被称为 Dokhtar-kosh,当且仅当路径上的字符经过重新排序后可以变成一个回文串。 求每个子树中最长的 Dokhtar-kosh 路径的长度。

题目描述

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. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF741D/ae6eaea25c446dd1a9c02c7621129601f3a81ec1.png)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.

输入输出格式

输入格式


The first line contains integer $ n $ ( $ 1<=n<=5·10^{5} $ ) — 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.

输出格式


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.

输入输出样例

输入样例 #1

4
1 s
2 a
3 s

输出样例 #1

3 1 1 0 

输入样例 #2

5
1 a
2 h
1 a
4 h

输出样例 #2

4 1 0 1 0