P7206 [COCI 2019/2020 #3] Lampice

Mirko decorates a Christmas tree with $N$ LED lights. Their colors are known, and they are connected by $(N-1)$ wires. After finishing, Mirko carefully admires his work. He is attracted by a special pattern called a "palindrome segment". A "palindrome segment" is a path from $u$ to $v$ such that the sequence of light colors along the path from $u$ to $v$ is the same as the sequence of light colors along the path from $v$ to $u$. Find the longest "palindrome segment" in the Christmas tree.

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, B$, indicating that $A$ and $B$ are connected by a wire.

Output the longest "palindrome segment" in the Christmas tree.

#### Constraints | Subtask | Score | Constraints | | :----------: | :----------: | :----------: | | $1$ | $17$ | $N \le 3000$ | | $2$ | $25$ | The $i$-th light is directly connected to the $(i+1)$-th light ($1 \le i \lt N$) | | $3$ | $31$ | At most $100$ lights are directly connected to another light | | $4$ | $37$ | None | For $100\%$ of the testdata, $1 \le N \le 5 \times 10^4, 1 \le A, B \le N, A \neq B$. #### Notes **The score of this problem is set according to the original COCI problem, with a full score of $110$.** **Translated from [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #3](https://hsin.hr/coci/archive/2019_2020/contest3_tasks.pdf) _T4 Drvca_.** Translated by ChatGPT 5