树上回文子序列

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定一棵带小写字母点权的树。记 $s(v,u)$ 为从 $v$ 到 $u$ 的简单路径上的字母串。求所有路径字符串的最长回文子序列长度的最大值。

注意，所求对象是子序列，不要求在路径字符串中连续。

输入格式

第一行包含测试组数 $t$。

每组测试数据的第一行包含顶点数 $n$，第二行包含一个长度为 $n$ 的小写字母串。接下来 $n-1$ 行每行包含两个整数 $u,v$，表示一条树边。

输出格式

对每组测试数据输出一个整数，表示答案。

样例输入 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\le t\le200$；
• $1\le n\le2000$，所有测试组的 $n$ 之和不超过 $2000$；
• 点权均为小写英文字母；
• 输入边构成一棵树。