显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned int TYPE;
const int maxn=10010;
const TYPE H=1000007;
int T,N,tot,son[maxn][2],hkey[maxn],ans[maxn],fa[maxn],Rt,deep[maxn],goat,head[maxn];
ll tag[maxn],nowl,nowr;
TYPE Hash[maxn],Pow[maxn];
char ch[maxn];
#define L(x) son[x][0]
#define R(x) son[x][1]
struct Edge{
int to,next,w;
}edge[maxn*2];
void Add(int x,int y){
edge[++tot].to=y;
edge[tot].next=head[x];
head[x]=tot;
}
int pre,scn,h1,h2;
#define p edge[i].to
void rebuild(int x,ll l,ll r){
if(!x)return;
tag[x]=(l+r)/2;
ll mid=(l+r)/2;
if(L(x))rebuild(L(x),l,mid);
if(R(x))rebuild(R(x),mid,r);
}
int rotate(int x,int k,ll l,ll r){
int y=son[x][k^1];
son[x][k^1]=son[y][k];
son[y][k]=x;
rebuild(y,l,r);
return y;
}
int rotate(int x,int k){
int y=son[x][k^1];
son[x][k^1]=son[y][k];
son[y][k]=x;
return y;
}
bool dcmp(int x,int y){
return (ch[x]<ch[y]||(ch[x]==ch[y]&&tag[fa[x]]<tag[fa[y]]));
}
void insert(int &rt,int x,ll l,ll r){
if(!rt){
rt=x;
tag[x]=(l+r)/2;
L(x)=R(x)=0;hkey[x]=rand()%10000000+1;
return;
}
ll mid=(l+r)>>1;
if(dcmp(x,rt))insert(L(rt),x,l,mid);
else insert(R(rt),x,mid,r);
if(L(rt)&&hkey[L(rt)]<hkey[rt])rt=rotate(rt,1,l,r);
else if(R(rt)&&hkey[R(rt)]<hkey[rt])rt=rotate(rt,0,l,r);
}
int query_pre(int x){
int now=Rt,maxid=0;
while(now){
if(dcmp(now,x)){
if(!maxid||tag[now]>tag[maxid])maxid=now;
now=R(now);
}
else now=L(now);
}
return maxid;
}
int query_scn(int x){
int now=Rt,minid=0;
while(now){
if(dcmp(x,now)){
if(!minid||tag[now]<tag[minid])minid=now;
now=L(now);
}
else now=R(now);
}
return minid;
}
bool check(int x,int y,int len){
if(Hash[x]-Hash[x-len]*Pow[len]==Hash[y]-Hash[y-len]*Pow[len])return 1;
return 0;
}
int erase(int rt,int x,ll l,ll r){
ll mid=(l+r)>>1;
if(rt==x){
if(!L(rt)){
rebuild(R(rt),l,r);
return R(rt);
}
if(!R(rt)){
rebuild(L(rt),l,r);
return L(rt);
}
if(hkey[L(rt)]<hkey[R(rt)])rt=rotate(rt,1),R(rt)=erase(R(rt),x,mid,r);
else rt=rotate(rt,0),L(rt)=erase(L(rt),x,l,mid);
goat=rt;nowl=l;nowr=r;
}
else if(tag[rt]<tag[x])R(rt)=erase(R(rt),x,mid,r);
else L(rt)=erase(L(rt),x,l,mid);
return rt;
}
int LCP(int x,int y){
int l=1,r=min(x,y),maxx=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(x,y,mid)){
maxx=max(maxx,mid);
l=mid+1;
}
else r=mid-1;
}
return maxx;
}
void check(){
cout<<"root"<<Rt<<endl;
for(int i=1;i<=N;i++){
cout<<i<<" "<<tag[i]<<" "<<L(i)<<" "<<R(i)<<endl;
}
}
void dfs(int x){
Hash[deep[x]]=Hash[deep[x]-1]*H+ch[x]-'a';
pre=query_pre(x),scn=query_scn(x);
if(pre)h1=LCP(deep[pre],deep[x]);else h1=0;
if(scn)h2=LCP(deep[scn],deep[x]);else h2=0;
insert(Rt,x,0,(1ll<<61));
// cout<<x<<" * "<<pre<<" "<<scn<<" "<<h1<<" "<<h2<<endl;
ans[x]=ans[fa[x]]+deep[x]-max(h1,h2);
for(int i=head[x];i;i=edge[i].next){
if(p==fa[x])continue;
deep[p]=deep[x]+1;
fa[p]=x;
dfs(p);
}
goat=0;
// cout<<"erase"<<x<<endl;
// cout<<"**"<<Rt<<endl;
Rt=erase(Rt,x,0,(1ll<<61));
// check();
if(goat)rebuild(goat,nowl,nowr);
}
void init(){
scanf("%d",&N);
memset(head,0,sizeof(head));
tot=0;
for(int i=1;i<N;i++){
int x,y;
scanf("%d%d",&x,&y);
Add(x,y);Add(y,x);
}
scanf("%s",ch+1);
deep[1]=1;fa[1]=0;
dfs(1);
for(int i=1;i<=N;i++)printf("%d\n",ans[i]);
}
int main(){
freopen("balsuffix.in","r",stdin);freopen("balsuffix.out","w",stdout);
srand(665543);
scanf("%d",&T);
Pow[0]=1;
for(int i=1;i<=10000;i++)Pow[i]=Pow[i-1]*H;
while(T--){
init();
}
return 0;
}
半汪