lb2003的个人博客

看见树上关于点对$(u,v)$的，通常就$\Theta(n\log n)$的点分治或者$\Theta(n)$的树形DP

那么这道题可以采用点分治的方法计算经过当前根节点$x$的合法路径数。

详细:https://www.cnblogs.com/dysyn1314/p/12371944.html

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define fin(s) freopen(s".in","r",stdin)
#define I inline 
using namespace std;
const int N=1e6+5,M=N<<1;const ull G=31;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct edge{int y,next;}a[N<<1];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
int siz[N],mx[N],n,m,root,sum;bool vis[N];
void get_root(int x,int f)
{
    siz[x]=1;mx[x]=0;
    for(int k=last[x],y;k;k=a[k].next)
    {
        if(vis[y=a[k].y]||y==f)continue;
        get_root(y,x);
        siz[x]+=siz[y];
        mx[x]=max(mx[x],siz[y]);
    }
    mx[x]=max(mx[x],sum-siz[x]);
    if(!root||mx[root]>mx[x])root=x;
}
void modify(int x,int f)
{
    siz[x]=1;
    for(int k=last[x],y;k;k=a[k].next)
    {
        if(vis[y=a[k].y]||y==f)continue ;
        modify(y,x);
        siz[x]+=siz[y];
    }
}
int mxd,pre[N],suf[N],ssuf[N],spre[N];ll ans;
ull h_pre[N],h_suf[N],pw[N];
char s[N],w[N],rootchar;
void calc(int x,int f,int dep,ull h)
{
    mxd=max(mxd,dep);
    h=h+1ull*w[x]*pw[dep-1];int cur=dep%m;
    if(h==h_pre[dep]){++pre[cur];if(rootchar==s[cur+1])ans+=ssuf[m-cur-1];}
    if(h==h_suf[dep]){++suf[cur];if(rootchar==s[m-cur])ans+=spre[m-cur-1];}
    for(int k=last[x],y;k;k=a[k].next)
    {
        if(vis[y=a[k].y]||y==f)continue;
        calc(y,x,dep+1,h);    
    }
}
void dfs(int x)
{
    modify(x,0);int mxD=0;
    rootchar=w[x];vis[x]=1;
    if(rootchar==s[1])++spre[0];
    if(rootchar==s[m])++ssuf[0];
    for(int k=last[x],y;k;k=a[k].next)
    {
        if(vis[y=a[k].y])continue;
        mxd=0;
        calc(y,x,1,0);mxD=max(mxD,mxd);
        for(int i=0;i<m&&i<=mxd;i++)
            spre[i]+=pre[i],pre[i]=0,
            ssuf[i]+=suf[i],suf[i]=0;
    }
    for(int i=0;i<m&&i<=mxD;i++)ssuf[i]=spre[i]=0;
    for(int k=last[x],y;k;k=a[k].next)
    {
        if(vis[y=a[k].y])continue;
        sum=siz[y],root=0;get_root(y,0);
        dfs(root);
    }
}
void Hash(char *s,ull *H)
{
    for(int i=m+1;i<=n;i++)s[i]=s[i-m];
    for(int i=1;i<=n;i++)H[i]=H[i-1]*G+s[i];
}
void clr()
{
    memset(last,0,sizeof(int)*(n+3));
    memset(vis,0,sizeof(bool)*(n+3));
    ans=0;len=0;
}
int main()
{
    pw[0]=1;for(int i=1;i<N-2;i++)pw[i]=pw[i-1]*G;
    int T;qr(T);while(T--)
    {
        qr(n),qr(m);clr();scanf("%s",w+1);for(int i=1;i<=n;i++)w[i]-='A';
        for(int i=1,x,y;i<n;i++)qr(x),qr(y),ins(x,y),ins(y,x);
        scanf("%s",s+1);for(int i=1;i<=m;i++)s[i]-='A';
        Hash(s,h_pre);reverse(s+1,s+m+1);Hash(s,h_suf);reverse(s+1,s+m+1);
        sum=n;root=0;get_root(1,0);
        dfs(root);
        qw(ans);puts("");
    }
}