看见树上关于点对$(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("");
}
}
最后一次更新于2020-05-14
0 条评论