deepseek

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

typedef unsigned long long ULL;

const int MAXN = 1000005;
const int MAXM = 1000005;
const ULL B = 1315423911ULL;

// 快速读入
const int BUF_SIZE = 1 << 20;
char buf[BUF_SIZE];
int buf_pos = 0, buf_len = 0;
inline char get_char() {
    if (buf_pos == buf_len) {
        buf_len = fread(buf, 1, BUF_SIZE, stdin);
        buf_pos = 0;
        if (buf_len == 0) return EOF;
    }
    return buf[buf_pos++];
}
inline int read_int() {
    char c = get_char();
    while (c < '0' || c > '9') c = get_char();
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = get_char();
    }
    return x;
}
void read_string(char *s) {
    char c = get_char();
    while (c < 'A' || c > 'Z') c = get_char();
    int p = 0;
    while (c >= 'A' && c <= 'Z') {
        s[p++] = c;
        c = get_char();
    }
    s[p] = '\0';
}

int n, m;
int char_val[MAXN];
int S_vals[MAXM];
bool removed[MAXN];

// 邻接表
int head[MAXN], to[MAXN * 2], nxt[MAXN * 2], edge_cnt = 0;
inline void add_edge(int u, int v) {
    to[edge_cnt] = v; nxt[edge_cnt] = head[u]; head[u] = edge_cnt++;
    to[edge_cnt] = u; nxt[edge_cnt] = head[v]; head[v] = edge_cnt++;
}

// 重心相关
int sz[MAXN], par[MAXN];

// 无限重复 S 的哈希
ULL powB[MAXN + MAXM + 5];
ULL pre_T[MAXN + MAXM + 5];
int T_len;

// 计数数组
int cntA[MAXM], cntB[MAXM];
int subA_buf[MAXN], subB_buf[MAXN];

// 遍历栈
struct State {
    int node, parent;
    int depth;      // down-path length (without c)
    ULL h_down;     // hash of c->...->node (without c)
    int lenA;       // up-path length (with c)
    ULL h_up;       // hash of node->...->c (with c)
} stk[MAXN];
int stk_top;

// 非递归找重心
int get_centroid(int start) {
    static int order[MAXN], stack[MAXN];
    int stack_top = 0;
    stack[stack_top++] = start;
    par[start] = -1;
    int order_len = 0;
    while (stack_top) {
        int x = stack[--stack_top];
        order[order_len++] = x;
        for (int e = head[x]; ~e; e = nxt[e]) {
            int y = to[e];
            if (y != par[x] && !removed[y]) {
                par[y] = x;
                stack[stack_top++] = y;
            }
        }
    }
    int total = 0;
    for (int i = order_len - 1; i >= 0; --i) {
        int x = order[i];
        sz[x] = 1;
        for (int e = head[x]; ~e; e = nxt[e]) {
            int y = to[e];
            if (y != par[x] && !removed[y]) {
                sz[x] += sz[y];
            }
        }
        if (i == 0) total = sz[x];
    }
    for (int i = 0; i < order_len; ++i) {
        int x = order[i];
        bool ok = true;
        if (total - sz[x] > total / 2) continue;
        for (int e = head[x]; ~e; e = nxt[e]) {
            int y = to[e];
            if (y != par[x] && !removed[y] && sz[y] > total / 2) {
                ok = false; break;
            }
        }
        if (ok) return x;
    }
    return -1;
}

ULL ans = 0;

// 处理经过重心 c 的所有路径
void process(int c) {
    int c_char = char_val[c];
    memset(cntA, 0, sizeof(int) * (m + 1));
    memset(cntB, 0, sizeof(int) * (m + 1));

    for (int e = head[c]; ~e; e = nxt[e]) {
        int v = to[e];
        if (removed[v]) continue;

        int subA_len = 0, subB_len = 0;

        // 初始化 c -> v
        stk_top = 0;
        stk[stk_top++] = {v, c, 1,
                          (ULL)char_val[v],
                          2,
                          (ULL)char_val[v] * powB[1] + (ULL)c_char};

        while (stk_top) {
            State s = stk[--stk_top];
            int node = s.node, parent = s.parent;
            int depth = s.depth;
            ULL h_down = s.h_down;
            int lenA = s.lenA;
            ULL h_up = s.h_up;

            // 向上路径
            if (h_up == pre_T[lenA]) {
                int r = lenA % m;
                subA_buf[subA_len++] = r;
                if (r == 0) ++ans;   // <node, c>
            }

            // 向下路径
            int rB = (m - depth % m) % m;
            ULL target = pre_T[rB + depth] - pre_T[rB] * powB[depth];
            if (h_down == target) {
                subB_buf[subB_len++] = rB;
                if (c_char == S_vals[0] && rB == 1) ++ans; // <c, node>
            }

            // 扩展子结点
            for (int ce = head[node]; ~ce; ce = nxt[ce]) {
                int child = to[ce];
                if (child == parent || removed[child]) continue;
                stk[stk_top++] = {child, node,
                                  depth + 1,
                                  h_down * B + (ULL)char_val[child],
                                  lenA + 1,
                                  (ULL)char_val[child] * powB[lenA] + h_up};
            }
        }

        // 与之前子树配对
        for (int i = 0; i < subA_len; ++i) {
            int r = subA_buf[i];
            ans += cntB[r];
        }
        for (int i = 0; i < subB_len; ++i) {
            int r = subB_buf[i];
            ans += cntA[r];
        }

        // 合并
        for (int i = 0; i < subA_len; ++i) cntA[subA_buf[i]]++;
        for (int i = 0; i < subB_len; ++i) cntB[subB_buf[i]]++;
    }
}

void decompose(int start) {
    int c = get_centroid(start);
    process(c);
    removed[c] = true;
    for (int e = head[c]; ~e; e = nxt[e]) {
        int v = to[e];
        if (!removed[v]) decompose(v);
    }
}

int main() {
    n = read_int(); m = read_int();
    char tmp_str[MAXN];
    read_string(tmp_str);
    for (int i = 1; i <= n; ++i) char_val[i] = tmp_str[i - 1] - 'A' + 1;

    memset(head, -1, sizeof(int) * (n + 1));
    for (int i = 1; i < n; ++i) {
        int u = read_int(), v = read_int();
        add_edge(u, v);
    }

    read_string(tmp_str);
    for (int i = 0; i < m; ++i) S_vals[i] = tmp_str[i] - 'A' + 1;

    // 构造无限重复 T，长度至少 n + m + 5
    T_len = 0;
    while (T_len < n + m + 5) {
        for (int i = 0; i < m && T_len < n + m + 5; ++i)
            T_len++;
    }
    // 填充 T_vals 并计算前缀哈希
    powB[0] = 1;
    pre_T[0] = 0;
    int idx = 0;
    for (int i = 0; i < T_len; ++i) {
        int val = S_vals[i % m];
        pre_T[i + 1] = pre_T[i] * B + (ULL)val;
        powB[i + 1] = powB[i] * B;
    }

    ans = 0;
    // 单点路径 <u, u>
    if (m == 1) {
        for (int i = 1; i <= n; ++i)
            if (char_val[i] == S_vals[0]) ++ans;
    }

    decompose(1);

    printf("%llu\n", ans);
    return 0;
}

orz

这题很难，同意的点赞