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

题目描述

给定一棵以 $1$ 号顶点为根的有根树，树中共有 $n$ 个顶点。每条边上写有一个小写英文字母，字母只会出现在 a 到 v 之间。

称一个字符串是 Dokhtar-kosh 的，当且仅当可以重新排列它的字符，使其变成一个回文串。等价地，这个字符串中至多只有一种字符出现奇数次。

对于每个顶点 $v$，考虑以 $v$ 为根的子树。你需要在这个子树内部选择一条简单路径，使得路径上所有边的字母按顺序组成的字符串是 Dokhtar-kosh 的，并使这条路径的长度尽可能大。路径长度按经过的边数计算。请输出每个顶点对应的最大长度。

输入格式

第一行一个整数 $n$，表示顶点数。

接下来 $n-1$ 行，第 $i$ 行描述顶点 $i+1$ 的父边，包含一个整数 $p_{i+1}$ 和一个小写字母 $c_{i+1}$，表示 $p_{i+1}$ 是 $i+1$ 的父亲，且边 $(p_{i+1}, i+1)$ 上写着字母 $c_{i+1}$。

输出格式

输出 $n$ 个整数，第 $i$ 个整数表示以顶点 $i$ 为根的子树中的答案。

样例

样例输入

3
1 a
1 b

样例输出

1 0 0

数据范围与约定

$1\le n\le 5\times 10^5$，$1\le p_i<i$，$c_i\in\{a,b,\ldots,v\}$。

说明

原需求中写作 CodeForces-741E，但对应的树上启发式合并题实际为 CodeForces-741D，本包按 CF741D 制作。