Solution - Hossam and (sub-)palindromic tree

又名：《最近 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\) 走一步之后的点是什么？

1. 类似于 lca 一样跳（？），我猜的。
2. 其实只需要每个点 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