#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long prime = 999983,m1=29,m2=31,sz[50100],n,p[50100],cp[50100],hash_value1[50100],hash_value2[50100],ans,pow_v1[50100],pow_v2[50100],d_ind[50100];
bool dead[50100],pel[50100],hash_table1[1000100],hash_table2[1000100];
vector<ll> g[50100];
string s;
// -> t*m+v
// <- t+v*pow()
void get_sz(ll start,ll parent)
{
sz[start] = 1;
for(ll next:g[start])
{
if(dead[next] ||parent == next)
continue;
get_sz(next,start);
sz[start] += sz[next];
}
}
ll get_centroid(ll start,ll parent,ll tree_sz)
{
for(ll next:g[start])
{
if(dead[next]||next==parent)
continue;
if(sz[next]>tree_sz/2)
return get_centroid(next,start,tree_sz);
}
return start;
}
ll left_push1(ll hash_v,ll v)
{
return (hash_v*m1+v)%prime;
}
ll left_push2(ll hash_v,ll v)
{
return (hash_v*m2+v)%prime;
}
ll right_add1(ll hash_v,ll v,ll ind)
{
return (hash_v+pow_v1[ind]*v)%prime;
}
ll right_add2(ll hash_v,ll v,ll ind)
{
return (hash_v+pow_v2[ind]*v)%prime;
}
void check_pel(ll start,ll parent,ll d,ll up1,ll up2,ll down1,ll down2)
{
up1 = left_push1(up1,(ll)(s[start]-'a'+1));
up2 = left_push2(up2,(ll)(s[start]-'a'+1));
down1 = right_add1(down1,(ll)(s[start]-'a'+1),d);
down2 = right_add2(down2,(ll)(s[start]-'a'+1),d);
hash_value1[start] = up1;
hash_value2[start] = up2;
if(up1==down1&&up2==down2)
pel[start] = true;
else
pel[start] = false;
for(ll next:g[start])
{
if(dead[next] || parent == next)
continue;
check_pel(next,start,d+1,up1,up2,down1,down2);
}
}
void update(ll start,ll parent)
{
hash_table1[hash_value1[start]] = true;
hash_table2[hash_value2[start]] = true;
for(ll next:g[start])
{
if(dead[next] || parent == next)
continue;
update(next,start);
}
}
void clear_hash(ll start,ll parent)
{
hash_table1[hash_value1[start]] = false;
hash_table2[hash_value2[start]] = false;
for(ll next:g[start])
{
if(dead[next] || parent == next)
continue;
clear_hash(next,start);
}
}
void cal_c(ll start,ll parent,ll l,ll d)
{
p[start] = parent;
d_ind[d] = start;
if(d==l)
{
cp[start] = start;
return;
}
cp[start] = -1;
for(ll next:g[start])
{
if(dead[next] || parent==next)
continue;
cal_c(next,start,l,d+1);
}
if(2*d-l>0)
cp[start] = d_ind[2*d-l];
}
bool dfs_pel(ll start,ll parent,ll l,ll d) // l is length of pel, d is depth, l-d for other sub tree, 2d-l+1>=0, up is better for calculate
{
if(d>l)
return false;
for(ll next:g[start])
{
if(next==parent||dead[next])
continue;
if(dfs_pel(next,start,l,d+1))
return true;
}
if(2*d-l<=0||!pel[cp[start]])
return false;
if(2*d-l-1==0)
return hash_table1[hash_value1[start]]&&hash_table2[hash_value2[start]];
ll pel_s1 = hash_value1[p[cp[start]]];
ll pel_s2 = hash_value2[p[cp[start]]];
ll hash_v1 = ((hash_value1[start]-pow_v1[l-d+1]*pel_s1)%prime+prime)%prime;
ll hash_v2 = ((hash_value2[start]-pow_v2[l-d+1]*pel_s2)%prime+prime)%prime;
return hash_table1[hash_v1]&&hash_table2[hash_v2];
}
bool centroid_decomposition(ll start,ll l)
{
get_sz(start,-1);
ll c = get_centroid(start,-1,sz[start]);
dead[c]=true;
for(ll next:g[c])
{
if(!dead[next]&¢roid_decomposition(next,l))
{
dead[c] = false;
return true;
}
}
ll root1 = left_push1((ll) 0,(ll)(s[c]-'a'+1));
ll root2 = left_push2((ll) 0,(ll)(s[c]-'a'+1));
hash_table1[root1] = true;
hash_table2[root2] = true;
check_pel(c,-1,0,(ll) 0,(ll) 0,(ll) 0,(ll) 0);
cal_c(c,-1,l,1);
/*cout<<c<<" "<<l<<"\n";
for(int i=0;i<n;i++)
cout<<hash_value[i]<<" ";
cout<<"\n";
for(int i=0;i<n;i++)
cout<<cp[i]<<" ";
cout<<"\n";
for(int i=0;i<n;i++)
cout<<pel[i]<<" ";
cout<<"\n";*/
for(ll next:g[c])
{
if(dead[next])
continue;
if(dfs_pel(next,c,l,2))
{
dead[c] = false;
clear_hash(c,-1);
return true;
}
update(next,c);
}
clear_hash(c,-1);
hash_table1[root1] = true;
hash_table2[root2] = true;
for(ll i = g[c].size()-1;i>=0;i--)
{
ll next = g[c][i];
if(dead[next])
continue;
if(dfs_pel(next,c,l,2))
{
dead[c] = false;
clear_hash(c,-1);
return true;
}
update(next,c);
}
clear_hash(c,-1);
dead[c] = false;
return false;
}
void init(ll n)
{
pow_v1[0] = (ll) 1;
pow_v2[0] = (ll) 1;
for(ll i=1;i<n;i++)
{
pow_v1[i] = pow_v1[i-1]*m1%prime;
pow_v2[i] = pow_v2[i-1]*m2%prime;
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
cin>>s;
init(n);
for(int i=0;i<n-1;i++)
{
ll a,b;
cin>>a>>b;
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
}
//odd
ll low = 0;
ll high = (n-1)/2;
while(low!=high)
{
ll mid=(low+high+1)/2;
if(centroid_decomposition(0,mid*2+1))
low = mid;
else
high = mid-1;
}
ans = 2*low+1;
//even
low = 0;
high = (n/2);
while(low!=high)
{
ll mid=(low+high+1)/2;
if(centroid_decomposition(0,mid*2))
low = mid;
else
high = mid-1;
}
ans = max(ans,low*2);
cout<<ans<<"\n";
}
