← 返回题目列表

Codeforces · 914/E

E. 树中的回文

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

给定一棵有 n 个顶点的树(连通的非循环无向图)。顶点从 1 到 n 编号,每个顶点分配一个从 a 到 t 的字符。

如果路径中标签的至少一个排列是回文,则称树中的路径是回文的。

对于每个顶点,输出经过它的回文路径的数量。

注意:从顶点 u 到顶点 v 的路径被认为与从顶点 v 到顶点 u 的路径相同,并且该路径对于其经过的每个顶点仅计数一次。

输入

第一行包含一个整数 n (2 ≤ n ≤ 2·105) — 树中的顶点数。

接下来的 n - 1 行每行包含两个整数 u 和 v (1 ≤ u, v ≤ n, u ≠ v),表示连接顶点 u 和顶点 v 的边。保证给定的图是一棵树。

下一行包含一个由从 a 到 t 的 n 个小写字符组成的字符串,其中第 i (1 ≤ i ≤ n) 个字符是树中顶点 i 的标签。

输出

在一行中打印n个整数,其中第i个是树中经过顶点i的回文路径的数量。

示例

输入 #1

5
1 2
2 3
3 4
3 5
abcbb

输出 #1

1 3 4 3 3

输入 #2

7
6 2
4 3
3 7
5 2
7 2
1 4
afefdfs

输出 #2

1 4 1 1 2 4 2

注意

在第一个示例案例中,以下路径是回文路径:

2 - 3 - 4

2 - 3 - 5

4 - 3 - 5

此外,所有仅包含一个顶点的路径都是回文路径。下面列出了第一个示例中的一些非回文路径:

1 - 2 - 3

1 - 2 - 3 - 4

1 - 2 - 3 - 5