COCI '19 Contest 3 #4 Lampice

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 5.0s
Memory limit: 512M

Problem types

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 \le N \le 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 \le A, B \le N, A \ne 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.


Subtask Score Constraints
1 17 N \le 3000
2 25 Light i is directly connected with light i+1 (1 \le i < N).
3 31 At most 100 lights are directly connected with exactly one other light.
4 37 No additional constraints.

Sample Input 1

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

Sample Output 1


Sample Input 2

1 2
1 3
3 4

Sample Output 2


Sample Input 3

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

Sample Output 3