时空限制

2S/128M

题目描述

给定一棵由 $n$ 个节点组成的树，节点编号为 $1$ 到 $n$。树的每条边上都有一个小写字母。

定义一条从节点 $u$ 到节点 $v$ 的路径字符串，为这条简单路径上所有边上的字母按顺序拼接成的字符串。

称一条路径 $(u, v)$ 是好的，当且仅当它的路径字符串，在重新排列字符顺序后，可以形成一个回文串。

求对于树中的每一个节点 $u$，计算存在多少个节点 $v$（$v \not = u$ ），使得路径 $(u, v)$ 是好的。

格式

输入格式

输入的第一行包含一个整数 $n$，表示节点的数量。

接下来 $n-1$ 行，每行包含两个整数 $u, v$ 和一个小写字母 $c$，表示节点 $u$ 和 $v$ 之间有一条边，边上的字母是 $c$。

输出格式

输出一行，包含 $n$ 个用空格隔开的整数，第 $i$ 个整数表示，以节点 $i$ 为起点的好路径的数量。

样例

样例输入 #1

5
1 2 a
2 3 a
3 4 b
3 5 c

样例输出 #1

4 2 4 2 2

样例解释 #1

对于 $u = 1$：

• $(1,2)$ 的路径字符串为 a。
• $(1,3)$ 的路径字符串为 aa。
• $(1,4)$ 的路径字符串为 aab，可以重排成 aba。
• $(1,5)$ 的路径字符串为 aac，可以重排成 aca。

对于 $u = 2$：

• $(2,1)$ 的路径字符串为 a。
• $(2,3)$ 的路径字符串为 a。

对于 $u = 3$：

• $(3,1)$ 的路径字符串为 aa。
• $(3,2)$ 的路径字符串为 a。
• $(3,4)$ 的路径字符串为 b。
• $(3,5)$ 的路径字符串为 c。

对于 $u = 4$：

• $(4,1)$ 的路径字符串为 baa，可以重排成 aba。
• $(4,3)$ 的路径字符串为 b。

对于 $u = 5$：

• $(5,1)$ 的路径字符串为 caa，可以重排成 aca。
• $(5,3)$ 的路径字符串为 c。

数据规模

对于 $40\%$ 的数据，$1 \leq n \leq 2000$。

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，边上的字母 $c$ 均为小写英文字母。且输入构成一棵树。