← 返回题目列表

Codeforces · 1771/D

D. Hossam 和(子)回文树

中文机器翻译题面 查看原题

Hossam 有一个未加权的树 $$$G$$$,顶点带有字母。

Hossam 将 $$$s(v, \, u)$$$ 定义为一个字符串,该字符串是通过记下 $$$G$$$ 树中从顶点 $$$v$$$ 到顶点 $$$u$$$ 的唯一简单路径上的所有字母而获得的。

字符串 $$$a$$$ 是字符串 $$$s$$$ 的子序列,如果 $$$a$$$ 可以通过删除几个(可能是零)字母从 $$$s$$$ 获得。例如,“dores”、“cf”和“for”是“codeforces”的子序列,而“decor”和“fork”则不是。

回文是从左到右和从右到左读相同的字符串。例如,“abacaba”是回文,但“abac”不是。

Hossam 将字符串 $$$s$$$ 的子回文定义为 $$$s$$$ 的子序列,即回文。例如,“k”、“abba”和“abhba”是字符串“abhbka”的子回文,但“abka”和“cat”不是。

Hossam 将字符串 $$$s$$$ 的最大子回文定义为 $$$s$$$ 的子回文,其长度是 $$$s$$$ 的所有子回文中的最大长度。例如,“abhbka”只有一个最大子回文——“abhba”。但也可能该字符串有几个最大子回文数:字符串“abcd”有$$$4$$$最大子回文数。

帮助 Hossam 找到 $$$G$$$ 树中所有 $$$s(v, \, u)$$$ 中最长的最大子回文的长度。

请注意,子回文是一个子序列,而不是子串。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 200$$$) — 测试用例的数量。

每个测试用例的第一行都有一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^3$$$) — 图中的顶点数。

第二行包含一个长度为$$$n$$$的字符串$$$s$$$,其中第$$$i$$$个符号表示顶点$$$i$$$上的字母。保证该字符串中的所有字符都是小写英文字母。

接下来的 $$$n - 1$$$ 行描述了树的边缘。每条边由两个整数 $$$v$$$ 和 $$$u$$$ 给出($$$1 \le v, \, u \le n$$$, $$$v \neq u$$$)。这两个数字意味着树中存在一条边 $$$(v, \, u)$$$。保证给定的边形成一棵树。

保证所有 $$$n$$$ 的总和不超过 $$$2 \cdot 10^3$$$。

输出

对于每个测试用例,输出一个整数 - 所有 $$$s(v, \, u)$$$ 中最长的最大子回文的长度。

示例

输入 #1

2
5
abaca
1 2
1 3
3 4
4 5
9
caabadedb
1 2
2 3
2 4
1 5
5 6
5 7
5 8
8 9

输出 #1

3
5

注意

在第一个示例中,最大子回文是在顶点 $$$1、\、3、\、5$$$ 中包含字母的“aaa”,或在顶点 $$$1、\、4、\、5$$$ 中包含字母的“aca”。

第一个示例中的树。

在第二个示例中,只有一个最大回文“bacab”,其顶点为 $$$4, \, 2, \, 1, \, 5, \, 9$$$ 中的字母。

第二个示例中的树。