题目内容

在一棵以 $1$ 号节点为根的家族族谱树中，共有 $n$ 位成员，每位成员都有一个专属的小写字母作为其纹章。

对于任意一位成员 $u$，考虑在其后代中选取两个成员 $x$ 和 $y$（允许 $x=y$），并满足：

• $u$ 是 $x$ 与 $y$ 的最近共同祖先；
• 从 $x$ 到 $u$ 路径上经过的节点数（包含 $x$ 和 $u$）等于从 $y$ 到 $u$ 路径上经过的节点数。

沿着 $x$ 到 $y$ 的唯一简单路径，依次收集每个节点的纹章字母，形成一个字符串。若该字符串是一个回文串，则称 $(x,y)$ 构成一个以 $u$ 为中心的“镜渊路径”。这条路径上的节点总数称为该镜渊路径的长度。

成员 $u$ 的“镜渊半径”定义为：所有以 $u$ 为中心的镜渊路径长度的最大值。特别地，当 $x=y=u$ 时，路径仅包含 $u$ 自身，长度总为 $1$，因此镜渊半径至少为 $1$。

请你求出每一位成员的镜渊半径。

数据规模：族谱成员数量 $n$ 满足 $1 \le n \le 10^5$，所有纹章均为小写英文字母。

输入描述

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示族谱成员的数量。 第二行包含一个长度为 $n$ 的字符串 $s$，其中第 $i$ 个字符表示编号为 $i$ 的成员的纹章字母。 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示成员 $u$ 与成员 $v$ 之间有一条直接的亲缘连线。输入保证构成一棵树。

输出描述

输出一行，包含 $n$ 个整数，用空格分隔，第 $i$ 个整数表示成员 $i$ 的镜渊半径。

样例1

输入

1
a

输出

1

说明

族谱只有 1 位成员，显然只能选取 $x=y=1$，路径仅包含自身，长度为 $1$。

样例2

输入

4
abcc
1 2
2 3
2 4

输出

1 3 1 1

说明

成员 2 拥有两个子嗣 3 和 4，它们的纹章均为 c。选取 $x=3, y=4$，$LCA(3,4)=2$，且 $dist(2,3)=dist(2,4)=1$，路径 $3 \to 2 \to 4$ 的字符串为 c b c，是一个回文串，长度 $2 \times 1 + 1 = 3$。 成员 1 只有一个子嗣 2，无法选取来自不同分支且深度相等的两个后代，因此只能选 $x=y=1$，长度为 1。成员 3 与 4 为叶节点，半径均为 1。

样例3

输入

5
abbcc
1 2
1 3
2 4
3 5

输出

5 1 1 1 1

说明

以 1 为中心，考虑深度 $d=1$：两个子节点 2 和 3 纹章均为 b，路径 2-1-3 构成回文 b a b，长度 $2 \times 1 + 1 = 3$；深度 $d=2$：后代 4（来自 2）与 5（来自 3）纹章均为 c，且从 1 到它们的向下路径字符串分别为 bc 和 bc，路径 4-2-1-3-5 字符串为 c b a b c，是回文，长度 $2 \times 2 + 1 = 5$。因此成员 1 的镜渊半径为 $\max(3,5)=5$。 成员 2 只有一个儿子 4，成员 3 只有一个儿子 5，成员 4 和 5 无后代，它们均只能获得长度 1。

样例4

输入

9
abbccccdd
1 2
1 3
2 4
2 5
3 6
3 7
4 8
6 9

输出

5 3 3 1 1 1 1 1 1

说明

成员 2：子嗣 4 和 5 纹章均为 c，路径 4-2-5 为回文 c b c，长度 $2 \times 1 + 1 = 3$；成员 3：子嗣 6 和 7 纹章均为 c，同样获得长度 $3$。 成员 1：深度 $d=1$ 时，2 和 3 的纹章 b 相同，长度 $3$；深度 $d=2$ 时，来自 2 的孙子 4（c）与来自 3 的孙子 6（c）可以配对，路径 4-2-1-3-6 对应字符串 c b a b c，长度 $5$；无更深配对。因此半径为 $\max(3,5)=5$。 其余节点 4、5、6、7、8、9 均只有单个分支或无分支，半径为 1。