C++11(clang++ 3.9) 解法, 执行用时: 984ms, 内存消耗: 20088K, 提交时间: 2019-03-09 15:05:14

#include<bits/stdc++.h>
#define debug(x) cout<<#x<<"="<<x<<endl
typedef unsigned long long ll;
using namespace std;
const int maxn = 1000009;
const int p = 31;
 
int first[maxn];
struct edg
{
	int next;
	int to;
}e[maxn<<1];
int e_sum;
ll mid;
int n,m,T,rt,sum,mx;
char str[maxn],temp[maxn];
ll ft[maxn],val[maxn],h1[maxn],h2[maxn];
int W[maxn],siz[maxn],cnt1[maxn],cnt2[maxn];
bool vis[maxn];
long long ans;
 
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void add_edg(int x,int y)
{
	e_sum++;
	e[e_sum].next=first[x];
	first[x]=e_sum;
	e[e_sum].to=y;
}
 
void ClearLove()
{
	memset(vis,0,sizeof vis);memset(first,0,sizeof first);
	e_sum=0;ans=0;
}
 
void find(int x,int f)
{
	W[x]=0;siz[x]=1;
	for(int i=first[x];i;i=e[i].next)
	{
		int w=e[i].to;
		if(vis[w]||w==f) continue;
		find(w,x);
		siz[x]+=siz[w];
		W[x]=max(W[x],siz[w]);
	}W[x]=max(W[x],sum-siz[x]);
	if(W[x]<W[rt]) rt=x;
}
void dfs(int x,int f,int step,ll now)
{
	if(now==h1[step]&&mid==temp[step%m+1]-'A'+1) ans+=cnt2[m-step%m-1]; // could be the head of ans =w=
	if(now==h2[step]&&mid==temp[m-step%m]-'A'+1) ans+=cnt1[m-step%m-1]; // could be the tail of ans =w=
	for(int i=first[x];i;i=e[i].next)
	{
		int w=e[i].to;
		if(w==f||vis[w]) continue;
		dfs(w,x,step+1,now+val[w]*ft[step]);
	}mx=max(mx,step);
}
void update(int x,int f,int step,ll now)
{
	if(now==h1[step]) cnt1[step%m]++;
	if(now==h2[step]) cnt2[step%m]++;
	for(int i=first[x];i;i=e[i].next)
	{
		int w=e[i].to;
		if(w==f||vis[w]) continue;
		update(w,x,step+1,now+val[w]*ft[step]);
	}
}
void solve(int x)
{
	vis[x]=1;mid=val[x];mx=0;
	cnt1[0]=cnt2[0]=1;
	if(m==1&&val[x]==h1[m]) ans++;
	for(int i=first[x];i;i=e[i].next)
	{
		int w=e[i].to;
		if(vis[w]) continue;
		dfs(w,x,1,val[w]);
		update(w,x,1,val[w]);
	}
	for(int i=0;i<=min(m,mx);i++) cnt1[i]=cnt2[i]=0;
	for(int i=first[x];i;i=e[i].next)
	{
		int w=e[i].to;
		if(vis[w]) continue;
		sum=siz[w];rt=0;
		find(w,0);solve(rt);
	}
}
 
int main()
{
	T=read();
	ft[0]=1;for(int i=1;i<=maxn-9;i++) ft[i]=ft[i-1]*p;
	while(T--)
	{
		ClearLove();
		n=read();m=read();
		scanf("%s",str+1);
		for(int i=1;i<=n;i++) val[i]=str[i]-'A'+1;
		for(int i=1;i<n;i++)
		{
			int x=read(),y=read();
			add_edg(x,y);add_edg(y,x);
		}
		scanf("%s",str+1);memcpy(temp,str,sizeof temp);
		for(int i=m+1;i<=n;i++) str[i]=str[i-m];
		for(int i=1;i<=n;i++) h1[i]=h1[i-1]*p+str[i]-'A'+1;reverse(str+1,str+1+m);
		for(int i=m+1;i<=n;i++) str[i]=str[i-m];
		for(int i=1;i<=n;i++) h2[i]=h2[i-1]*p+str[i]-'A'+1;
		sum=n;rt=0;W[0]=n+1;
		find(1,0);solve(rt);
		printf("%d\n",ans);
	}
	return 0;
}