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

题目描述

以防有人错过了：Arpa 的土地上有很多美丽的女孩。

Arpa 有一棵有根树（连通无环图），包含 $n$ 个顶点。顶点编号为 $1$ 到 $n$，顶点 $1$ 是根结点。这棵树的每条边上都写有一个小写字母。Mehrdad 是“Dokhtar-kosh”事物的粉丝。如果一个字符串可以重排使得它变成回文串，则称该字符串为 Dokhtar-kosh 字符串。

如图所示：

Arpa 向你询问：对于每一个顶点 $v$，在以 $v$ 为根的子树中，最长的、使其路径上的字母组成 Dokhtar-kosh 字符串的简单路径的长度是多少。

输入格式

第一行包含整数 $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}$。

输出格式

输出 $n$ 个整数。第 $i$ 个整数表示以第 $i$ 个顶点为根的子树中，最长的、路径上的字母可以组成 Dokhtar-kosh 字符串的简单路径的长度。

输入输出样例 #1

输入 #1

4
1 s
2 a
3 s

输出 #1

3 1 1 0 

输入输出样例 #2

输入 #2

5
1 a
2 h
1 a
4 h

输出 #2

4 1 0 1 0 

说明/提示

由 ChatGPT 5 翻译