题目描述

Mirko 准备用 $n$ 个 LED 灯来装饰圣诞树。这 $n$ 个灯通过了 $n−1$ 根电线连接在一起，任意两个灯之间都能通过电线互相到达。并且我们知道所有灯的颜色。

装饰结束后，Mirko 发现了很多有趣的图案，其中他最感兴趣的是 palindromic segments。一个 palindromic segments 是一条灯 $u$ 和灯 $v$ 之间的路径，满足从 $u$ 到 $v$ 经过的灯的颜色序列和从 $v$ 到 $u$ 经过的灯的颜色序列相同。

Mirko 想要知道最长的 palindromic segments 有多长。一个 palindromic segments 长度定义为这条路径上灯的个数。

输入格式

第一行包含一个整数 $n$，表示灯的个数。

第二行包含一个长度为 $n$ 的字符串，仅由小写字母组成，其中第 $i$ 个字符表示第 $i$ 个灯的颜色。

接下里 $n−1$ 行，每行包含两个整数 $A$ 和 $B$，表示灯 $A$ 和灯 $B$ 之间有一条电线直接相连。

输出格式

仅一行，包含一个整数表示最长的 palindromic segments 的长度。

7
imanade
1 2
2 3
3 4
4 5
5 6
6 7

3

4
aabb
1 2
1 3
3 4

2

8
acdbabcd
1 6
6 7
6 3
3 4
4 5
5 2
8 5

5

数据规模与约定

本题按照原题设置 Subtask。

对于 $100\%$ 的数据，$1\le n \le 5\times 10^4$，$1\le A,B\le n,A\neq B$。

题目来源

题目译自 COCI2019-2020 Contest#3 T4 Lampice。