解题思路

对于节点 $i$，若选择两个后代节点 $u,v$，满足：

$LCA(u,v)=i$

$dist(u,i)=dist(v,i)=d$

那么路径 $u \to v$ 的点数为：

题目内容

小美有一棵 $n$ 个节点的树，根节点为 1，第 $i$ 个节点上有一个小写字母 $s_i$。

对于一个节点 $i$ 的权值 $val_i$，定义为：Condition: 若节点 $i$ 可以从以 $i$ 为根节点的子树中选取两个节点 $u, v$（$u, v$ 可以相同），满足 $\text{LCA}(u,v) = i$，且 $\text{dist}(u,i) = \text{dist}(v,i)$，且满足 $u \to v$ 的简单路径上的节点字母依次拼接后的字符串是一个回文串。其中 $\text{LCA}(u,v)$ 表示 $u, v$ 的最近公共祖先、$\text{dist}(u,v)$ 表示 $u, v$ 两点间简单路径的点数。

当然这样的 $u, v$ 可能有很多，我们令

现在请你输出每个节点的 $val_i$。

名词解释

• 子树：对于树中某个节点，其与所有后代节点构成的集合称为该节点的子树
• 简单路径：树上任意两个节点之间的路径，不经过重复的点和边。在树上，任意两个节点间有且仅有一条简单路径。
• 最近公共祖先：在一棵有根树中，节点 $u$ 和 $v$ 的最近公共祖先指同时位于“根到 $u$ 的路径”和“根到 $v$ 的路径”上的节点中，距离根节点最远的一个。
• 回文串：若一个字符串从左向右读与从右向左读完全相同，则称其为回文串。

输入描述

第一行一个整数 $n$（$1 \le n \le 10^5$），表示节点个数。

第二行一个长度为 $n$ 的字符串 $s$，表示节点上的字母。

接下来 $n-1$ 行，每行两个整数 $u, v$（$1 \le u, v \le n$），表示当前无向边连接 $u, v$ 两点。

输入保证是一棵树。

输出描述

输出包含 $n$ 个整数，以空格隔开，第 $i$ 个数表示第 $i$ 个节点的 $val_i$。

样例1

输入

7
aaaaaaa
1 2
1 3
2 4
2 5
3 6
3 7

输出

5 3 3 1 1 1 1

样例2

输入

3
baa
1 2
1 3

输出

3 1 1