求卡常

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
const int N=1000010,M=2000010,INF=0x3f3f3f3f;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline void swap(int &x,int &y){x^=y^=x^=y;}
int head[N],ver[M],Next[M],tot;
int T,n,m,rt,ans,sz[N],vis[N],f[N][2],c[N];
char s[N],t[N];
ull h0[N],h1[N],h2[N],p[N];
void add(int x,int y){
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void get_rt(int x,int fa,int sum){
	sz[x]=1;
	int flg=1;
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(vis[y]||y==fa)continue;
		get_rt(y,x,sum);
		sz[x]+=sz[y];
		if(sz[y]>sum/2)flg=0;
	}
	if(flg&&sum-sz[x]<=sum/2)rt=x;
}
void dp(int x,int dep){
	h2[dep]=h2[dep-1]*131+s[x]-'A'+1;
	if(dep<m){
		f[dep][0]=(h2[dep]==h0[m]-p[dep]*h0[m-dep]);//suffix
		f[dep][1]=(h2[dep]==h1[m]-p[dep]*h1[m-dep]);//prefix
	}
	else{
		f[dep][0]=(f[dep-m][0]&&h2[dep]-p[m]*h2[dep-m]==h0[m]);
		f[dep][1]=(f[dep-m][1]&&h2[dep]-p[m]*h2[dep-m]==h1[m]);
	}
}
void calc(int x,int fa,int dep,int op){
	dp(x,dep);
	c[dep%m]+=op*f[dep][1];
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(vis[y]||y==fa)continue;
		calc(y,x,dep+1,op);
	}
}
void dfs(int x,int fa,int dep){
	sz[x]=1;
	dp(x,dep);
	ans+=f[dep][0]*c[(m-dep%m+1)%m];
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(vis[y]||y==fa)continue;
		dfs(y,x,dep+1);
		sz[x]+=sz[y];
	}
}
void solve(int x){
	vis[x]=1;
	f[0][0]=f[0][1]=1;
	calc(x,0,1,1);
	ans+=c[0];
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(vis[y])continue;
		calc(y,x,2,-1);
		dfs(y,x,2);
		calc(y,x,2,1);
	}
	calc(x,0,1,-1);
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(vis[y])continue;
		get_rt(y,x,sz[y]);
		solve(rt);
	}
}
void solve(){
	ans=tot=0;
	cin>>n>>m>>s+1;
	for(int i=1;i<=n;i++)head[i]=vis[i]=0;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);add(y,x);
	}
	cin>>t+1;
	p[0]=1;
	for(int i=1;i<=m;i++){
		h0[i]=h0[i-1]*131+t[i]-'A'+1;
		h1[i]=h1[i-1]*131+t[m-i+1]-'A'+1;
		p[i]=p[i-1]*131;
	}
	get_rt(1,0,n);
	solve(rt);
	cout<<ans<<'\n';
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--)solve();
	return 0;
}