Codeforces Round #837 (Div. 2)D （最大回文字串+树）

题目描述

给定一颗有n(n<=2e3)个顶点的树，每个顶点有一个点权（字符）,定义s(u,v)为从u到v的简单路径
所经过的点权形成的字符串的最大回文字串
求对于所有s(u,v)求最大回文子串

解题思路：

首先我们看到了关键词“回文字串”,所以我们先考虑如果对于一个普通的字符串如何求最大回文字串：
我们定义cal(i,j)为从i到j的最大回文子串：
如果 i == j ,cal( i , j ) = 1
如果 i+1 == j:

• 如果 s[i] == s[j], cal( i , j ) = 2;
• 如果 s[i] != s[j], cal( i , j ) = 1;

如果有s[i] == s[j] ,cal(i,j) = cal(i+1,j-1)+2;
最后一种情况 cal( i , j ) = max( cal( i , j-1 ),cal( i+1 , j) );

int cal2(int u,int v){
	if(u == v) return 1;
	if(u+1 == v){
		if(a[u] == a[v]) return 2;
		return 1;
	}
	if(f[u][v] != -1) return f[u][v];
	int res = 0;
	
	res = max(cal(u+1,v),cal(u,v-1));
	if(a[u] == a[v]){
		res = max(res,cal(u+1,v-1)+2);
	}
	return f[u][v] = res;
}

而在树上对于两个节点u,v，他们的前一个，后一个节点实际上也是确定的，所以只要对每个节点跑一次dfs,求出每个节点的nex，然后套入同样的思路即可

代码实现:

#include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 2e3 + 10, inf = 0x3f3f3f3f;
vector<int> e[N];
char a[N];
int f[N][N];
int nex[N][N];
void dfs(int u,int fa,int to){
	nex[u][to] = fa;
	for(auto v:e[u]){
		if(v == fa) continue;
		dfs(v,u,to);
	}
}
int cal(int u,int v){
	if(u == v) return 1;
	if(nex[u][v] == v){
		if(a[u] == a[v]) return 2;
		return 1;
	}
	if(f[u][v] != -1) return f[u][v];
	int res = 0;
	
	res = max(cal(nex[u][v],v),cal(u,nex[v][u]));
	if(a[u] == a[v]){
		res = max(res,cal(nex[u][v],nex[v][u])+2);
	}
	return f[u][v] = res;
}

void solve() {
	int n;
	cin >> n;
	string s;
	cin>>s;
	for (int i = 1; i <= n; ++i) {
		e[i].clear();
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			f[i][j] = -1;
			nex[i][j] = 0;
		}
	}
	for (int i = 1; i <= n; ++i) a[i] = s[i - 1];
	for (int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for(int i = 1;i <= n;++i) dfs(i,0,i);
	int maxn = 0;
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= n;++j){
			maxn = max(maxn,cal(i,j));
		}
	}
	cout<<maxn<<endl;


}
int tt;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	tt = 1;
	cin >> tt;
	while (tt--) solve();


	return 0;
}

ps:本文章仅作为本人的学习笔记,便于复习,思路参考与严格鸽Codeforces Round #837 (Div. 2) C(因数分解) D(树上DP）%%%