← 返回题目列表

Codeforces · 741/D

D. Arpa 的字母标记树和 Mehrdad 的 Dokhtar-kosh 路径

中文机器翻译题面 查看原题

以防万一有人错过了:我们在阿尔帕的土地上有很棒的女孩。

Arpa 有一个由 n 个顶点组成的有根树(连通无环图)。顶点编号为 1 到 n,顶点 1 是根。这棵树的每条边上都写着一封信。迈赫达德是 Dokhtar-kosh 事物的粉丝。如果我们可以将字符串中的字符打乱,使其成为回文,他将字符串称为 Dokhtar-kosh。

他问Arpa,对于每个顶点v,v的子树中形成Dokhtar-kosh字符串的最长简单路径的长度是多少。

输入

第一行包含整数 n (1 ≤ n ≤ 5·105) — 树中的顶点数。 接下来是

(n - 1) 行,其中第 i 行包含一个整数 pi + 1 和一个字母 ci + 1(1 ≤ pi + 1 ≤ i,ci + 1 为小写英文字母,介于 a 和 v 之间),这意味着节点 pi + 1 和 i + 1 之间有一条边,并且这条边上写有一个字母 ci + 1。

输出

打印 n 个整数。其中第 i 个应该是形成 Dokhtar-kosh 字符串的第 i 个顶点的子树中最长的简单路径的长度。

示例

输入 #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