题意

Sol

直接考虑点分治+hash匹配

设\(up[i]\)表示\(dep \% M = i\)的从下往上恰好与前\(i\)位匹配的个数

\(down\)表示\(dep \% M = i\)的从上往下恰好与后\(i\)位匹配的个数

暴力转移即可

复杂度：\(O(nlog^2n)??\)

代码写起来有一车边界

#include
    
     #define ull unsigned long long #define LL long long #define int long long #define siz(v) ((int)v.size())using namespace std;const int MAXN = 1e6 + 10, INF = 1e10 + 10;inline int read() {    char c = getchar(); int x = 0, f = 1;    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x * f;}int N, M, Root, siz[MAXN], mx[MAXN], Siz, dep[MAXN], up[MAXN], down[MAXN], su[MAXN], sd[MAXN];LL ans;bool det[MAXN];char a[MAXN], b[MAXN];vector
     
       v[MAXN];ull hs[MAXN], hp[MAXN], po[MAXN], base = 1331;map
      
        mp;void FindRoot(int x, int fa) {    siz[x] = 1; mx[x] = 0;    for(int i = 0; i < siz(v[x]); i++) {        int to = v[x][i];        if(to == fa || det[to]) continue;        FindRoot(to, x);        siz[x] += siz[to]; mx[x] = max(mx[x], siz[to]);    }    mx[x] = max(mx[x], Siz - siz[x]);    if(mx[x] < mx[Root]) Root = x;}int dfs(int x, int fa, ull now) {    siz[x] = 1;    dep[x] = dep[fa] + 1;    now = now * base + a[x];    if(hp[dep[x]] == now) up[(dep[x] - 1) % M + 1]++, ans += sd[M - (dep[x] - 1) % M];    if(hs[dep[x]] == now) down[(dep[x] - 1) % M + 1]++, ans += su[M - (dep[x] - 1) % M];   // printf("%d %d\n", x, ans);    int td =1;    for(int i = 0; i < siz(v[x]); i++) {        int to = v[x][i];        if(to == fa || det[to]) continue;        td = max(td, dfs(to, x, now) + 1);         siz[x] += siz[to];    }    return td;}void work(int x) {    int tk = 0, tmp = 0;    det[x] = 1; dep[x] = 1; su[1] = sd[1] = 1;//tag;    for(int i = 0; i < siz(v[x]); i++) {           int to = v[x][i];           if(det[to]) continue;        tk = min(M, dfs(to, x, a[x]) + 1), tmp = max(tmp, tk);        for(int j = 1; j <= tk; j++) su[j] += up[j], sd[j] += down[j], up[j] = down[j] = 0;    }    for(int i = 1; i <= tmp; i++) su[i] = sd[i] = 0;    for(int i = 0; i < siz(v[x]); i++) {        int to = v[x][i];        if(to == x || det[to]) continue;        Siz = siz[to]; Root = 0; FindRoot(to, x);         work(Root);    }}void init() {    for(int i = 1; i <= N; i++) v[i].clear();    memset(det, 0, sizeof(det));    memset(siz, 0, sizeof(siz));    memset(mx, 0, sizeof(mx));    ans = 0;    }void solve() {    N = read(); M = read();    init();    scanf("%s", a + 1);    for(int i = 1; i <= N - 1; i++) {        int x = read(), y = read();        v[x].push_back(y); v[y].push_back(x);    }    for(int i = 1; i <= N; i++) reverse(v[i].begin(), v[i].end());    scanf("%s", b + 1); po[0] = 1;    for(int i = 1; i <= N; i++) {        hp[i] = hp[i - 1] + b[(i - 1) % M + 1] * po[i - 1];        hs[i] = hs[i - 1] + b[M - (i - 1) % M] * po[i - 1];        po[i] = base * po[i - 1];    }    Siz = N; mx[0] = INF; Root = 0; FindRoot(1, 0);    work(1);     printf("%d\n", ans);}signed main() {    freopen("a.in", "r", stdin);    for(int T = read(); T; T--, solve());    return 0;}