COCI 2019/2020 - Contest 3 - Lampice

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 5.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2019/2020 - Contest 3
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Mirko mua một cây thông cho lễ Giáng sinh sắp đến và quyết định sẽ trang trí nó bằng đèn Giáng sinh. Đèn Giáng sinh gồm ~N~ bóng đèn LED nối với nhau bởi ~(N-1)~ dây điện sao cho tất cả bóng đèn đều được nối với nhau. Ngoài ra, chúng ta còn biết cả màu sắc của mỗi bóng đèn.

Sau khi trang trí cây thông, Mirko tự hào ngắm nhìn kiệt tác của mình. Sau một lúc, anh bắt đầu để ý các họa tiết khác nhau trên cây, và đặc biệt kinh ngạc bởi các xâu đối xứng. Xâu đối xứng được định nghĩa là một đoạn giữa hai bóng đèn ~u~ và ~v~ sao cho dãy màu sắc của các bòng đèn đi từ ~u~ đến ~v~ giống hệt dãy màu sắc của các bòng đèn đi từ ~v~ đến ~u~. Hãy xác định độ dài lớn nhất cùa các xâu đối xứng (đo bởi số lượng bóng đèn trên xâu).

Input

Dòng đầu tiên chứa số nguyên ~N~ ~(1 \leq N \leq 50\:000)~.

Dòng tiếp theo chứa một mảng gồm ~N~ chữ cái viết thường từ bảng chữ cái Tiếng Anh, trong đó chữ cái thứ ~i~ thể hiện màu sắc của bóng đèn thứ ~i~.

Mỗi dòng trong số ~(N−1)~ dòng tiếp theo chứa hai số nguyên ~A~ and ~B~ ~(1 \leq A, B \leq N, A \neq B)~, cho biết bóng đèn ~A~ và bóng đèn ~B~ được nối trực tiếp bởi dây điện.

Output

Một số nguyên duy nhất là độ dài lớn nhất cùa các xâu đối xứng.

Subtask

  • ~7~ test có ~N \leq 3000~
  • ~6~ test khác thỏa mãn bóng đèn ~i~ được nối trực tiếp với bóng đèn ~i+1~ ~(1 \leq i < N)~.
  • ~6~ test khác có nhiều nhất ~100~ bóng đèn được nối trực tiếp với chính xác một bóng đèn khác.
  • ~14~ test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

3

Sample Input 2

4
aabb
1 2
1 3
3 4

Sample Output 2

2

Sample Input 3

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

Sample Output 3

5

Comments

Please read the guidelines before commenting.


There are no comments at the moment.