Những ngày Tết đến, xuân về, trên khắp mọi nẻo đường, chúng ta đều sẽ bắt gặp những màu sắc rực rỡ của hoa mai, hoa đào, của những cửa hàng trưng bày vật dụng trang trí Tết. Trên con đường đi hàng ngày cũng thấy dường như sẽ được khoác lên màu áo mới, hay ở những công trình, công ty, chúng ta điều sẽ bắt gặp những hình ảnh trang trí ngụ ý Xuân đang về. Ở đâu chúng ta cũng điều thấy một màu Tết đang đến gần, đặc biệt hơn chính là Tết ở ngay trong căn nhà của chúng ta. Chính vì thế mà việc trang trí nhà ngày Tết rất là quan trọng.
Cây cảnh, hoa kiểng là những vật trang trí tết không thể thiếu cho gia đình trong năm mới. Việc lựa chọn loại hoa, loại cây để chưng tết là vấn đề quan trọng, mang lại may mắn cho gia đình trong năm mới. Những nhánh tầm xuân khẳng khiu nhưng lại thu hút người nhìn bởi sắc màu tươi trẻ cùng sức sống lâu bền. Loài hoa sống đời nhỏ nhắn nhưng lại mang màu sắc rực rỡ và sức sống bền bỉ và mang ý nghĩa cầu chúc một năm mới dồi dào sức khỏe cho cả gia đình. Màu vàng của hoa mai từ lâu được xem là màu tượng trưng cho sự giàu sang, phú quý. Mang cây hoa mai về nhà vào dịp Tết có đồng nghĩa với mong muốn một năm mới phát tài, giàu sang.
Nyan Cat là một coder có kinh nghiệm fix bug dày dặn, cũng là một người rất thích vẻ đẹp và ý nghĩa của cái loại cây. Tuy vậy, vì đống bugs của mình mà mèo ta không được công ty thưởng tiền chơi tết. Thế nên Nyan Cat quyết định sẽ săn sale ngày 30 tết - thời điểm mọi gian hàng chuẩn bị đóng cửa. Chú mèo đã may mắn tậu được cho mình một loại cây có tên là ~G~ cực rẻ và cực ưng ý để thêm sắc Tết cho căn nhà của mình. Cây ~G~ được miêu tả gồm ~n~ đỉnh, mỗi đỉnh chứa một chữ cái latinh, các cạnh không có trọng số.
Nyan Cat định nghĩa ~s(u, v)~ là chuỗi ký tự đạt được khi viết các chữ cái latinh trên các đỉnh thuộc đường đi từ ~u~ tới ~v~ trên cây ~G~.
Một palindrome là một chuỗi khi đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Ví dụ abcba
, k
là một palindrome còn abcc
và nyan
thì không.
Một sub-palindrome của một chuỗi ~a~ là một chuỗi con của ~a~, đồng thời là một palindrome. Ví dụ a
và acca
là một sub-palindrome của abcca
còn ab
và abc
thì không.
Để nhận được lì xì của Nyan Cat, bạn cần cho biết độ dài dài nhất của các sub-palindrome của tất cả chuỗi ~s(u, v)~.
Input
Dòng thứ nhất chứa số nguyên ~n~ - số đỉnh của cây.
Dòng thứ hai chứa chuỗi ~s~ có độ dài ~n~ cho biết đỉnh ~i~ chứa chữ cái ~s_{i}~.
~n-1~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~u~ và ~v~ ~(1\le u,v \le n)~ cho biết có cạnh nối từ ~u~ tới ~v~.
Output
Gồm một dòng cho biết độ dài dài nhất của các sub-palindrome của tất cả chuỗi ~s(u, v)~.
Scoring
- Subtask 1 (30%): ~n \le 60~.
- Subtask 2 (30%): các đỉnh có nhiều nhất ~2~ cạnh nối và ~n \le 2 \times 10^3~.
- Subtask 3 (40%): ~n \le 2\times 10^3~.
Sample Input
5
dbaca
1 2
1 3
3 4
4 5
Sample Ouput
3
Bình luận