临时抱佛脚之点分治（虽然听起来很强但是就是感觉哪就里是有暴点力不啊对）
对于模式字符串，我们先把它延伸到n的长度，正反hash
然后大力点分治，强行求它所管理的的子树的f值
f[i]表示和hash匹配到第i位的串数，至于为什么是二维就不说了:)
sf[i]表示当前重心管理的子节点的f之和，用于合并子树答案
对于答案的更新，假如当前正着匹配到第i位，那么就可以加上倒着匹配到当前位置的答案
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; int n; struct node { int x,y,next; }a[2100000];int len,last[1100000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } char ts[1100000]; LL ha[2][1100000];int m; LL ans,f[2][1100000],sf[2][1100000]; bool v[1100000]; int getlength(int x,int fr,int L,LL h) { h=h*27+(LL(ts[x]-'A'+1)); if(h==ha[0][L])f[0][(L-1)%m+1]++,ans+=sf[1][m-(L-1)%m]; if(h==ha[1][L])f[1][(L-1)%m+1]++,ans+=sf[0][m-(L-1)%m]; int mxL=1; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(v[y]==false&&y!=fr) mxL=max(mxL,getlength(y,x,L+1,h)+1); } return mxL; } //----------get_ans------------------- int sum,rt,tot[1100000],G[1100000]; void getrt(int x,int fr) { tot[x]=1;G[x]=0; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(v[y]==false&&y!=fr) { getrt(y,x); tot[x]+=tot[y]; G[x]=max(G[x],tot[y]); } } if(fr!=0)G[x]=max(G[x],sum-tot[x]); if(rt==0||G[x]<G[rt])rt=x; } void divi(int x) { v[x]=true;int mmax=1; sf[0][1]=sf[1][1]=1; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(v[y]==false) { LL h=(LL(ts[x]-'A'+1)); int L=getlength(y,x,2,h)+1; mmax=max(mmax,L); for(int i=1;i<=L;i++) sf[0][i]+=f[0][i],sf[1][i]+=f[1][i],f[0][i]=f[1][i]=0; } } for(int i=1;i<=mmax;i++)sf[0][i]=sf[1][i]=0; //~~~~~~~~~get_ans for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(v[y]==false) { sum=tot[y],rt=0; getrt(y,0);divi(rt); } } } //-----------点分治---------------------------- char ss[1100000]; int main() { freopen("data.in","r",stdin); freopen("1.out","w",stdout); int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); scanf("%s",ts+1); len=0;memset(last,0,sizeof(last)); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); ins(x,y);ins(y,x); } scanf("%s",ss+1); ha[0][0]=0LL;ha[1][0]=0LL;LL cf=1LL; for(int i=1;i<=n;i++) { ha[0][i]=ha[0][i-1]+cf*(LL(ss[(i-1)%m+1]-'A'+1)); ha[1][i]=ha[1][i-1]+cf*(LL(ss[m-(i-1)%m]-'A'+1)); cf=cf*27LL; } ans=0; memset(v,false,sizeof(v)); sum=n,rt=0; getrt(1,0);divi(rt); printf("%lld ",ans); } return 0; }