ref不是太懂
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef unsigned long long ull;
int T, n, m, hea[1000005], cnt, uu, vv, rnd[1000005], rot, siz[1000005];
int tot, sf[1000005], sg[1000005], ff[1000005], gg[1000005];
ull bse[1000005], hs1[1000005], hs2[1000005], ans;
char ss[1000005], tt[1000005];
bool vis[1000005];
struct Edge{
int too, nxt;
}edge[2000005];
void rn(int &x){
char ch=getchar();
x = 0;
while(ch<'0' || ch>'9') ch = getchar();
while(ch>='0' && ch<='9'){
x = x * 10 + ch - '0';
ch = getchar();
}
}
void add_edge(int fro, int too){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
hea[fro] = cnt;
}
void getRoot(int x, int f){
rnd[x] = 0;
siz[x] = 1;
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(!vis[t] && t!=f){
getRoot(t, x);
siz[x] += siz[t];
rnd[x] = max(rnd[x], siz[t]);
}
}
rnd[x] = max(rnd[x], tot-siz[x]);
if(rnd[x]<rnd[rot]) rot = x;
}
int dfs(int x, int f, int d, ull hx){
siz[x] = 1;
hx = hx * 131 + ss[x];
if(hs1[d]==hx){
ff[(d-1)%m+1]++;
ans += sg[m-(d-1)%m];
}
if(hs2[d]==hx){
gg[(d-1)%m+1]++;
ans += sf[m-(d-1)%m];
}
int tmp=1;
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(!vis[t] && t!=f){
siz[x] += siz[t];
tmp = max(tmp, dfs(t, x, d+1, hx)+1);
}
}
return tmp;
}
void work(int x){
vis[x] = true;
sf[1] = sg[1] = 1;
int tmp=0;
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(!vis[t]){
int k=min(m, dfs(t, x, 2, ss[x])+1);
tmp = max(tmp, k);
for(int j=1; j<=k; j++){
sf[j] += ff[j];
sg[j] += gg[j];
ff[j] = gg[j] = 0;
}
}
}
for(int i=1; i<=tmp; i++)
sf[i] = sg[i] = 0;
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(!vis[t]){
rot = 0;
tot = siz[t];
getRoot(t, x);
work(rot);
}
}
}
int main(){
cin>>T;
while(T--){
rn(n); rn(m);
scanf("%s", ss+1);
memset(hea, 0, sizeof(int)*(n+1));
memset(vis, 0, sizeof(bool)*(n+1));
cnt = ans = rot = 0;
tot = n;
for(int i=1; i<n; i++){
rn(uu); rn(vv);
add_edge(uu, vv);
add_edge(vv, uu);
}
scanf("%s", tt+1);
bse[0] = 1;
for(int i=1; i<=n; i++){
bse[i] = bse[i-1] * 131;
hs1[i] = hs1[i-1] + tt[(i-1)%m+1] * bse[i-1];
hs2[i] = hs2[i-1] + tt[m-(i-1)%m] * bse[i-1];
}
rnd[0] = 0x3f3f3f3f;
getRoot(1, 0);
work(rot);
printf("%llu
", ans);
}
return 0;
}