题目描述
Problem Description
Mirko decorates a Christmas tree with $N$ LED lights, each of a known color, connected by $(N-1)$ wires.
After completing his work, Mirko appreciates his creation. He is particularly fascinated by a pattern called "palindromic segment." A "palindromic segment" is a path from $u$ to $v$ such that the sequence of colors of the lights from $u$ to $v$ is the same as the sequence from $v$ to $u$.
Determine the longest "palindromic segment" in the Christmas tree.
Input Format
The first line contains an integer $N$, the number of LED lights.
The second line contains a string of $N$ lowercase English letters, where the $i$-th letter represents the color of the $i$-th light.
The next $(N-1)$ lines each contain two integers $A$ and $B$, indicating that there is a wire connecting $A$ and $B$.
Output Format
Output the length of the longest "palindromic segment" in the Christmas tree.
Sample Input and Output
Input Sample #1
7
imanade
1 2
2 3
3 4
4 5
5 6
6 7
Output Sample #1
3
Input Sample #2
4
aabb
1 2
1 3
3 4
Output Sample #2
2
Input Sample #3
8
acdbabcd
1 6
6 7
6 3
3 4
4 5
5 2
8 5
Output Sample #3
5
Notes
Data Range and Constraints
| Subtask | Score | Data Range and Constraints |
|---|---|---|
| $1$ | $17$ | $N \le 3000$ |
| $2$ | $25$ | The $i$-th light is directly connected to the $(i+1)$-th light ($1 \le i < N$) |
| $3$ | $31$ | At most $100$ lights are directly connected to another light |
| $4$ | $37$ | No additional constraints |
For $100\%$ of the data, $1 \le N \le 5 \times 10^4, 1 \le A,B \le N, A \neq B$.
Notes
This problem's score is set according to the original COCI contest, with a full score of $110$.
The problem is translated from COCI2019-2020 CONTEST #3 T4 Drvca.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分