又名：《最近 vjudge 题全部罚坐》。
唯一 Trick：回文序列，就想区间 dp！时间复杂度 \(O(n ^ 2)\)！
如果是序列：\(f_{l, r}\) 表示 \([l, r]\) 的最长回文子序列，\(f_{l, r} = \max(f_{l + 1, r}, f_{l, r - 1}, f_{l + 1, r - 1} + [s_l = s_r])\)，\(s\) 是字符串。很 trivial。
但是这是在树上！怎么知道 \(u\) 往 \(v\) 走一步之后的点是什么？
- 类似于 lca 一样跳（？），我猜的。
- 其实只需要每个点 dfs 一次预处理，总共 \(O(n ^ 2)\) 就行了。还可以顺便处理出两点之间的距离（相当于序列上的 \(len = r - l + 1\)），所以有时候大道至简（？）。
namespace liuzimingc {
const int N = 2e3 + 5;
#define endl '\n'
int T, n, f[N][N], go[N][N];
char s[N];
vector<int> e[N];
vector<pair<int, int>> sta[N];
void dfs(int rt, int g, int u, int fa, int len) {
go[rt][u] = g;
sta[len].push_back(make_pair(rt, u));
for (const int &v : e[u]) {
if (v == fa) continue;
dfs(rt, !len ? v : g, v, u, len + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> T;
while (T--) {
cin >> n >> (s + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
f[i][j] = go[i][j] = 0;
for (int i = 1; i <= n; i++) sta[i].clear(), e[i].clear(), f[i][i] = 1;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
f[u][v] = f[v][u] = 1 + (s[u] == s[v]);
}
for (int i = 1; i <= n; i++) dfs(i, i, i, i, 0);
for (int len = 2; len <= n; len++)
for (const auto &i : sta[len]) {
int l = i.first, r = i.second;
f[l][r] = max({ f[go[l][r]][r], f[l][go[r][l]], f[go[l][r]][go[r][l]] + (s[l] == s[r] ? 2 : 0) });
}
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
ans = max(ans, f[i][j]);
cout << ans << endl;
}
return 0;
}
} // namespace liuzimingc