#P15660. [Bulgarian2025训练营]Lights彩灯

    ID: 14872 传统题 3000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-二分答案点分治双哈希子串哈希正反哈希判回文哈希表DFS 序

[Bulgarian2025训练营]Lights彩灯

题目描述

Kris 选了一棵圣诞树,并决定用彩灯装饰它。

彩灯共有 NN 个,编号为 11 到 NN,由 N−1N-1 根导线连接,并保证所有彩灯连通,也就是说这些彩灯构成一棵树。每个彩灯都有一种颜色,用一个小写英文字母表示。

Kris 观察这些彩灯时,发现了所谓的回文段:对于两个固定的彩灯 uu 和 vv,考虑树上从 uu 到 vv 的简单路径。如果沿 u→vu\to v 得到的颜色序列,和沿 v→uv\to u 得到的颜色序列完全相同,则这条路径上的彩灯序列称为一个回文段。

请求出最长回文段包含的彩灯数量。

输入格式

第一行包含一个整数 NN,表示彩灯数量。

第二行包含一个长度为 NN 的小写英文字母串,第 ii 个字符表示第 ii 个彩灯的颜色。每个字母代表一种颜色。

接下来 N−1N-1 行,每行两个整数 A,BA,B,表示彩灯 AA 和彩灯 BB 之间有一根导线直接相连。

输出格式

输出一行一个整数,表示最长回文段的长度。

数据范围

  • 1≤N≤500001 \le N \le 50000
  • 1≤A,B≤N1 \le A,B \le N,A≠BA\ne B

子任务

子任务 分值 限制
1 15 N≤3000N\le 3000
2 20 彩灯 ii 与彩灯 i+1i+1 直接相连,即整棵树是一条链
3 30 至多有 100 个叶子节点
4 35 无额外限制

样例 1

输入

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

输出

3

说明

所有彩灯连成一条链,最长回文段为 a-n-a,长度为 33。

样例 2

输入

4
aabb
1 2
1 3
3 4

输出

2

样例 3

输入

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

输出

5