시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB1241969.375%

문제

Mirko chose a Christmas tree for the upcoming holidays and decided to decorate it with Christmas lights. Christmas lights contain N LED lights that are connected via (N − 1) conductive wires such that all of the lights are connected. Additionally, we know the color of each Christmas light.

After he decorated the tree, Mirko proudly stared at his masterpiece. After a while, he started noticing different patterns. Among those patterns, he was particularly amazed by so-called palindromic segments. Palindromic segment is a segment of Christmas lights on the path between two fixed lights, u and v, such that the array of colors on a path from u to v is exactly the same as the array of colors on the path from v to u. Determine the length of the longest palindromic segment expressed in the number of lights on that segment.

입력

The first line contains an integer N (1 ≤ N ≤ 50 000) from the task description.

The next line contains an array of N lowercase letters from the English alphabet where the i-th letter represents the color of the i-th Christmas light.

Each of the next (N − 1) lines contains two integers A and B (1 ≤ A, B ≤ N, A 6= B), which denote that lights A and B are directly connected by a conducting wire.

출력

The first line of output should contain the length of the longest palindromic segment.

서브태스크

번호배점제한
117

N ≤ 3000

225

Light i is directly connected with light i + 1 (1 ≤ i < N).

331

At most 100 lights are directly connected with exactly one other light.

437

No additional constraints.

예제 입력 1

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

예제 출력 1

3

예제 입력 2

4
aabb
1 2
1 3
3 4

예제 출력 2

2

예제 입력 3

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

예제 출력 3

5

채점 및 기타 정보

  • 예제는 채점하지 않는다.