#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> mp[25010];
#define N 50010
#define int long long
int palin[N],vis[N],pw[N],hsh[N],sz[N],val[N],ans,rt,B=31,mod=1e9+7;
vector<int>adj[N],V{0};
void dfssz(int n,int p,int tot){
palin[n]=0;
int mx=0;
sz[n]=1;
for(auto i:adj[n])
if(i-p&&!vis[i]) {
dfssz(i,n,tot),
sz[n]+=sz[i],
mx=max(mx,sz[i]);
}
if(sz[n]*2>=tot&&mx*2<=tot)
rt=n;
}
void calcdfs(int n,int p,int l,int d,int h){
if(d>l||ans) return;
if(d<=l/2)
ans|=mp[d][(hsh[n]-val[V[1]]*pw[d]%mod+mod)%mod];
hsh[n]=(hsh[p]*B+val[n])%mod;
h=(h+pw[d]*val[n])%mod;
palin[n]=hsh[n]==h;
for(auto i:adj[n])
if(!vis[i]&&i-p)
calcdfs(i,n,l,d+1,h);
}
void upddfs(int n,int p,int l,int d){
if(ans||d>l) return;
V.push_back(n);
int c;
if(d+l/2>=l&&palin[c=V[2*d-l]])
mp[l-d][(hsh[n]-hsh[c]*pw[l-d]%mod+mod)%mod]=1;
for(auto i:adj[n])
if(i-p&&!vis[i])
upddfs(i,n,l,d+1);
V.pop_back();
}
void cent(int n,int s,int l){
if(ans)
return;
dfssz(n,0,s);
dfssz(n=rt,0,s);
palin[n]=1;
vis[n]=1;
V.push_back(n);
for(auto i:adj[n]) if(!vis[i])
calcdfs(i,n,l,1,val[n]),
upddfs(i,n,l,2);
if(mp[0][0])
ans=1;
for(int i=0;i<=min(l/2,MD);i++)
mp[i].clear();
reverse(adj[n].begin(),adj[n].end());
for(auto i:adj[n]) if(!vis[i])
calcdfs(i,n,l,1,val[n]),
upddfs(i,n,l,2);
if(mp[0][0])
ans=1;
for(int i=0;i<=min(l/2,MD);i++)
mp[i].clear();
V.pop_back();
for(auto i:adj[n])
if(!vis[i])
cent(i,sz[i],l);
}
signed main() {
pw[0]=1;
for(int i=1;i<N;i++)
pw[i]=pw[i-1]*B%mod;
cin.tie(0)->sync_with_stdio(0);
int n;
string str;
cin>>n>>str;
for(int i=1;i<=n;i++)
val[i]=str[i-1]-'`';
if(n==1)
return puts("1"),0;
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
int l=0,r=n/2;
while(l<r){
int mid=l+r+1>>1;
for(int i=1;i<=n;i++)
palin[i]=vis[i]=ans=0;
cent(1,n,mid*2+1);
if(ans)
l=mid;
else r=mid-1;
}
int l1=l,r1=n/2;
while(l1<r1){
int mid=l1+r1+1>>1;
for(int i=1;i<=n;i++)
palin[i]=vis[i]=ans=0;
cent(1,n,mid*2);
if(ans)
l1=mid;
else r1=mid-1;
}
cout<<max(l1*2,l*2+1)<<'\n';
}
Compilation message
lampice.cpp: In function 'void cent(long long int, long long int, long long int)':
lampice.cpp:56:28: error: 'MD' was not declared in this scope
56 | for(int i=0;i<=min(l/2,MD);i++)
| ^~
lampice.cpp:64:28: error: 'MD' was not declared in this scope
64 | for(int i=0;i<=min(l/2,MD);i++)
| ^~
lampice.cpp: In function 'int main()':
lampice.cpp:91:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
91 | int mid=l+r+1>>1;
| ~~~^~
lampice.cpp:101:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
101 | int mid=l1+r1+1>>1;
| ~~~~~^~
