Description：

一棵树每个点上有一个字符，给出一个字符串 $S$ ，求树上有多少路径构成的字符串可以由 $S$ 重复若干次得到。

$1\leqslant n\leqslant 10^6$

Solution：

树上路径问题，考虑点分治，字符串问题，发现不是很好用数据结构维护，于是考虑哈希，我们先预处理一个 $hash[0/1][n]$ 表示长度为 $n$ 的前缀 $/$ 后缀的哈希值，然后在点分治的时候可以求出某条路径的哈希值，如果和预处理的值相等就把他加到一个桶里，位置为长度 $\bmod {len}$ ，然后统计一下贡献就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 1000010

char getc()

{

	register char c = getchar();

	while(!isupper(c))c = getchar();

	return c;

}

char c[MAXN],s[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

#define INF 0x3f3f3f3f

#define BASE 29ll

#define HASH 1000000007ll

int prehash[MAXN],sufhash[MAXN];

int pows[MAXN];

int root,siz[MAXN],d[MAXN],si;

bool vis[MAXN];

int ans;

void getroot(int k,int fa)

{

	siz[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa || vis[e[i].to])continue;

		getroot(e[i].to,k);

		siz[k] += siz[e[i].to];

		d[k] = max(d[k],siz[e[i].to]);

	}

	d[k] = max(d[k],si - siz[k]);

	if(d[k] < d[root])root = k;

	return;

}

int cntpre[MAXN],cntsuf[MAXN];

vector< pair<int,int> > bas;

int maxdep;

void dfs(int k,int fa,int dep,int hash)

{

	maxdep = max(maxdep,dep);

	bas.push_back(make_pair(dep,hash));//cout << k << " " << dep << " " << hash << endl;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa || vis[e[i].to])continue;

		dfs(e[i].to,k,dep + 1,(BASE * hash + c[e[i].to]) % HASH);

	}

	return;

}

void calc(int rt)

{//cout << " : " << rt << endl;

	maxdep = 0;

	cntpre[0] = cntsuf[0] = 1;

	for(int i = lin[rt];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dfs(e[i].to,rt,1,c[e[i].to]);

		for(vector< pair<int,int> >::iterator it = bas.begin();it != bas.end();++it)

		{

			if(it -> second == sufhash[it -> first] && c[rt] == s[m - it -> first % m])ans += cntpre[m - it -> first % m - 1];

			if(it -> second == prehash[it -> first] && c[rt] == s[it -> first % m + 1])ans += cntsuf[m - it -> first % m - 1];

		}

		for(vector< pair<int,int> >::iterator it = bas.begin();it != bas.end();++it)

		{

			if(it -> second == sufhash[it -> first])++cntsuf[it -> first % m];

			if(it -> second == prehash[it -> first])++cntpre[it -> first % m];

		}

		bas.clear();//cout << " -> " << ans << endl;

	}

	for(int i = 0;i <= maxdep;++i)cntpre[i] = cntsuf[i] = 0;//cout << rt << " ans : " << ans << endl;

	return;

}

void divide(int rt)

{

	vis[rt] = true;

	calc(rt);

	for(int i = lin[rt];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		root = 0;si = siz[e[i].to];

		getroot(e[i].to,0);

		divide(root);

	}

	return;

}

void work()

{

	ans = 0;

	memset(lin,0,sizeof(lin));

	edgenum = 0;

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)c[i] = getc() - 'A';

	for(int i = 1;i < n;++i)add(rd(),rd());

	for(int i = 1;i <= m;++i)s[i] = getc() - 'A';

	pows[0] = 1;

	for(int i = 1;i <= n;++i)pows[i] = BASE * pows[i - 1] % HASH;

	int l = m;

	while(l < n)l += m;

	for(int i = 1;i <= n;++i)prehash[i] = (prehash[i - 1] + 1ll * pows[i - 1] * s[(i - 1) % m + 1] % HASH) % HASH;

	for(int i = 1;i <= n;++i)sufhash[i] = (sufhash[i - 1] + 1ll * pows[i - 1] * s[(l - i) % m + 1] % HASH) % HASH;

	//for(int i = 1;i <= n;++i)cout << prehash[i] << " ";cout << endl;

	//for(int i = 1;i <= n;++i)cout << sufhash[i] << " ";cout << endl;

	root = 0;d[0] = INF;si = n;

	memset(vis,false,sizeof(vis));

	getroot(1,0);

	divide(root);

	cout << ans << endl;

	return;

}

int main()

{

	int testcases = rd();

	while(testcases--)work();

	return 0;

}