#include<iostream> #include<string> #include<vector> using namespace std; vector <int> a[100005]; int d[100005],t[100005],u[100005],i,x,y,n,mx,tst; bool pr[100005],v[100005]; string s; void df(int x) { int i; v[x]=1; for (i=0;i<a[x].size();i++) if (v[a[x][i]]==0) { t[a[x][i]]=x; df(a[x][i]); } } void dfs(int x) { int i; v[x]=1; if (2*d[x]-pr[x]>mx) mx=2*d[x]-pr[x]; for (i=0;i<a[x].size();i++) if (v[a[x][i]]==0) { if ((u[x]!=1) && (s[a[x][i]-1]==s[t[u[x]]-1])) { d[a[x][i]]=d[x]+1; u[a[x][i]]=t[u[x]]; pr[a[x][i]]=pr[x]; } else if (s[x-1]==s[a[x][i]-1]) { d[a[x][i]]=1; u[a[x][i]]=x; pr[a[x][i]]=0; } else { d[a[x][i]]=1; u[a[x][i]]=a[x][i]; pr[a[x][i]]=1; } dfs(a[x][i]); } } int main() { cin >> tst; while (tst--) { cin >> n >> s; for (i=1;i<n;i++) { cin >> x >> y; a[x].push_back(y); a[y].push_back(x); } mx=0; for (i=1;i<=n;i++) v[i]=0; df(1); for (i=1;i<=n;i++) d[i]=v[i]=0; d[1]=u[1]=1; dfs(1); cout << mx << "\n"; } return 0; }