解题思路
对于节点 i，若选择两个后代节点 u,v，满足：
LCA(u,v)=i
dist(u,i)=dist(v,i)=d
那么路径 u→v 的点数为：
P4845.第4题-树上操作
题目内容
小美有一棵 n 个节点的树，根节点为 1，第 i 个节点上有一个小写字母 si。
对于一个节点 i 的权值 vali，定义为：Condition: 若节点 i 可以从以 i 为根节点的子树中选取两个节点 u,v（u,v 可以相同），满足 LCA(u,v)=i，且 dist(u,i)=dist(v,i)，且满足 u→v 的简单路径上的节点字母依次拼接后的字符串是一个回文串。其中 LCA(u,v) 表示 u,v 的最近公共祖先、dist(u,v) 表示 u,v 两点间简单路径的点数。
当然这样的 u,v 可能有很多，我们令
vali=u,v∈Conditionmaxdist(u,v)
现在请你输出每个节点的 vali。
名词解释
- 子树：对于树中某个节点，其与所有后代节点构成的集合称为该节点的子树
- 简单路径：树上任意两个节点之间的路径，不经过重复的点和边。在树上，任意两个节点间有且仅有一条简单路径。
- 最近公共祖先：在一棵有根树中，节点 u 和 v 的最近公共祖先指同时位于“根到 u 的路径”和“根到 v 的路径”上的节点中，距离根节点最远的一个。
- 回文串：若一个字符串从左向右读与从右向左读完全相同，则称其为回文串。
输入描述
第一行一个整数 n（1≤n≤105），表示节点个数。
第二行一个长度为 n 的字符串 s，表示节点上的字母。
接下来 n−1 行，每行两个整数 u,v（1≤u,v≤n），表示当前无向边连接 u,v 两点。
输入保证是一棵树。
输出描述
输出包含 n 个整数，以空格隔开，第 i 个数表示第 i 个节点的 vali。
样例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
