rt，过样例了，但是 #1 WA #2#3 TLE。

Code：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

typedef long long ll;
typedef unsigned long long ull;

ull ans;
int c;
int n, m;
int ch[N], S[N];
queue<int> q;
struct edge{
	int to, next;
};
edge e[2 * N];
int head[N], cnt;
ull ksm[N], _pre[N], _suf[N], hash_pre[N], hash_suf[N];

int pre[N], suf[N];

inline void add(int u, int v){
	e[++cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}

inline void csh(){
	ksm[0] = 1;
	for(int i = 1; i <= n; ++i){
		ksm[i] = ksm[i - 1] * 26;
	}
	for(int i = 1; i <= n; ++i){
		_pre[i] = _pre[i - 1] * 26 + S[(i - 1) % m + 1];
	}
	for(int i = 1, j = m; i <= j; ++i, --j){
		swap(S[i], S[j]);
	}
	for(int i = 1; i <= n; ++i){
		_suf[i] = _suf[i - 1] * 26 + S[(i - 1) % m + 1];
	}
	return ;
}

int jds[N], mxzs[N], deep[N];
bool vis[N];

void find_zx(int u, int fa){
	q.push(u);
	jds[u] = 1;mxzs[u]=0;
	for(int i = head[u]; i; i = e[i].next){
		int v = e[i].to;
		if(v == fa || vis[v]) continue;
		find_zx(v, u);
		jds[u] += jds[v];
		mxzs[u] = max(mxzs[u], jds[v]);
	}
	return ;
}

void dfs1(int u, int fa){
	deep[u] = deep[fa] + 1;
	hash_pre[u] = hash_pre[fa] + ch[u] * ksm[deep[u]];
	//hash_suf[u] = hash_suf[fa] * 26 + ch[u];
	if(hash_pre[u] == _pre[deep[u] + 1]){
		int len = m - deep[u] % m;len %= m;
		//if((deep[u] + 1) % m == 0) len = 0;
		ans += suf[len];
	}
	if(hash_pre[u] == _suf[deep[u] + 1]){
		int len = m  - deep[u]  % m;len%=m;
		//if((deep[u] + 1) % m == 0) len = 0;
		ans += pre[len];
	}
	for(int i = head[u]; i; i = e[i].next){
		int v = e[i].to;
		if(vis[v] || v == fa) continue;
		dfs1(v, u);
	}
	return ;
}

queue<int> qu;

void dfs2(int u, int fa){
	if(hash_pre[u] == _pre[deep[u] + 1]){
		if(!pre[(deep[u] + 1) % m]) qu.push((deep[u] + 1) % m);
		pre[(deep[u] + 1) % m]++;
		//if(deep[u] % m == 0) len = 0;
	}
	if(hash_pre[u] == _suf[deep[u] + 1]){
		if(!suf[(deep[u] + 1) % m]) qu.push((deep[u] + 1) % m);
		suf[(deep[u] + 1) % m]++;
		//if(deep[u] % m == 0) len = 0;
	}
	for(int i = head[u]; i; i = e[i].next){
		int v = e[i].to;
		if(vis[v] || v == fa) continue;
		dfs2(v, u);
	}
	return ;
}

void dfz(int root){
//	memset(jds, 0, sizeof jds);
//	memset(mxzs, 0, sizeof mxzs);
	find_zx(root, -1);
	int all = jds[root];
	for(int i = 1; i <= n; ++i){
		if(mxzs[i]){
			mxzs[i] = max(mxzs[i], all - jds[i]);
			if(mxzs[i] < mxzs[root]) root = i;
		}
	}
	//cout << root << endl;
//	memset(deep, 0, sizeof deep);
//	memset(hash_pre, 0, sizeof hash_pre);
//	memset(hash_suf, 0, sizeof hash_suf);
//	memset(suf, 0, sizeof suf);
//	memset(pre, 0, sizeof pre);
	suf[0] = 1, pre[0] = 1;
	deep[root] = 0;
	hash_pre[root] = ch[root], hash_suf[root] = ch[root];
	for(int i = head[root]; i; i = e[i].next){
		int v = e[i].to;
		if(vis[v]) continue;
		dfs1(v, root);
		dfs2(v, root);
	}
	vis[root] = 1;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		jds[u] = 0;
		mxzs[u] = 0;
		deep[u] = 0;
		hash_pre[u] = 0;
		hash_suf[u] = 0;
	}
	while(!qu.empty()){
		int u = qu.front();
		qu.pop();
		suf[u] = 0, pre[u] = 0;
	}
	//cout<<root<<" "<<ans<<endl;
	for(int i = head[root]; i; i = e[i].next)
		if(!vis[e[i].to])
			dfz(e[i].to);

	return ;
}

int main(){
	//freopen("std.txt","r",stdin);
	scanf("%d", &c);
	while(c--){
		memset(vis, 0, sizeof vis);
		memset(head, 0, sizeof head);
		memset(e, 0, sizeof e);
		cnt = 0;
		scanf("%d%d", &n, &m);
		for(int i = 1; i <= n; ++i){
			char _ch = getchar();
			while(_ch < 'A' || _ch > 'Z') _ch = getchar();
			ch[i] = _ch - 'A';
		}
		for(int i = 1; i < n; ++i){
			int u, v;
			scanf("%d%d", &u, &v);
			add(u, v);
			add(v, u);
		}
		for(int i = 1; i <= m; ++i){
			char _ch = getchar();
			while(_ch < 'A' || _ch > 'Z') _ch = getchar();
			S[i] = _ch - 'A';
		}
		csh();
		dfz(1);
		printf("%lld\n", ans);
		ans = 0;
	}
	return 0;
}