题解：树上回文路径计数

题目分析

给定一棵树，每条边上有一个字符（0或1）。需要统计所有点对 $(x,y)$（$x < y$），使得从 $x$ 到 $y$ 的路径上的边字符按顺序组成的字符串是回文串。

这是一个经典的树上回文路径计数问题，需要高效处理大规模数据（$n \leq 50000$）。

解题思路

核心思想

使用点分治 + AC自动机 + 回文理论的组合方法：

1. 点分治：分解树结构，降低问题规模
2. AC自动机：处理字符串匹配和回文性质
3. Border理论：利用回文串的周期性质优化计数

关键技术

• 重心分解：$O(n \log n)$ 处理树结构
• 双哈希：判断字符串回文性
• 周期优化：根据周期大小采用不同统计策略

算法步骤

1. 点分治框架：寻找重心，递归处理子树
2. AC自动机构建：插入路径字符，构建fail指针
3. 回文路径统计：利用哈希和周期性质计数
4. 去重处理：避免重复统计

完整代码

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

#define pb push_back
#define ll long long

const int N = 1e5 + 5;
const int H = 1e9 + 9;
const int bas = 229;
const int B = 7;

int n, rt, tot, sz[N];
ll Ans = 0;
bool vis[N];
vector<array<int, 2>> G[N];

// 模运算工具函数
int adc(int a, int b) {
    return a + b >= H ? a + b - H : a + b;
}

int dec(int a, int b) {
    return a < b ? a - b + H : a - b;
}

int mul(int a, int b) {
    return 1ll * a * b % H;
}

// AC自动机类，用于处理回文路径
struct ACAM {
    int idx = 0;                    // 节点计数器
    int tr[N][2];                   // Trie树
    int pw[N];                      // 基数幂
    int fl[N];                      // fail指针
    int f[N][20];                   // 倍增数组
    int nxt[N], jp[N];              // 回文相关指针
    int hs[N][2];                   // 正反哈希值
    int d[N];                       // 节点深度
    int c[N];                       // 节点计数
    int w[B + 5][B + 5];            // 小周期计数数组
    int len[N], s[N];               // 临时数组
    ll ans = 0;                     // 当前答案
    
    vector<int> E[N];               // fail树
    vector<array<int, 3>> V[N];     // 周期信息
    vector<array<int, 3>> Q[N];     // 查询数组

    // 初始化AC自动机
    void init() {
        for (int i = 0; i <= idx; i++) {
            fl[i] = tr[i][0] = tr[i][1] = nxt[i] = jp[i] = 0;
            hs[i][0] = hs[i][1] = d[i] = c[i] = 0;
            E[i].clear();
            V[i].clear();
            Q[i].clear();
        }
        idx = 1;
        ans = 0;
        nxt[1] = jp[1] = 1;
    }

    // 创建新节点
    int nwnode(int p, int x) {
        if (!tr[p][x]) {
            tr[p][x] = ++idx;
            d[idx] = d[p] + 1;
            
            // 计算正反哈希值
            hs[idx][0] = adc(mul(hs[p][0], bas), x);
            hs[idx][1] = adc(hs[p][1], mul(x, pw[d[idx] - 1]));

            // 判断是否为回文串
            if (hs[idx][0] == hs[idx][1]) {
                nxt[idx] = idx;
            } else {
                nxt[idx] = nxt[p];
            }
            jp[idx] = nxt[p];
        }
        c[tr[p][x]]++;
        return tr[p][x];
    }

    // 构建fail指针
    void getfail() {
        // 初始化根节点的子节点
        for (int i : {0, 1}) {
            tr[0][i] = 1;
        }
        
        queue<int> q;
        q.push(1);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int i : {0, 1}) {
                int v = tr[u][i];
                if (!v) {
                    tr[u][i] = tr[fl[u]][i];
                } else {
                    fl[v] = tr[fl[u]][i];
                    q.push(v);
                }
            }

            E[fl[u]].pb(u);

            // 处理回文相关信息
            if (u > 1 && nxt[u] == u) {
                f[u][0] = jp[u];
                for (int i = 1; i <= 16; i++) {
                    f[u][i] = f[f[u][i - 1]][i - 1];
                }

                int x = u;
                for (int i = 16; i >= 0; i--) {
                    if (d[f[x][i]] > d[u] / 2) {
                        x = f[x][i];
                    }
                }

                V[u] = V[f[x][0]];
                V[u].pb({d[x], d[u], d[u] - d[jp[u]]});
            }
        }
    }

    // 二分查找满足条件的节点
    int find(int x, int dep) {
        int l = 1, r = dep, res = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (d[len[mid]] <= x) {
                res = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return res;
    }

    // 计算回文路径数量
    void calc(int u, int dep) {
        len[dep] = u;
        s[d[u]] += c[u];

        // 更新小周期计数
        for (int i = 1; i < B; i++) {
            w[i][d[u] % i] += c[u];
        }

        // 同一节点的路径对
        ans += 1ll * c[u] * (c[u] - 1) / 2;

        // 处理周期信息
        for (auto t : V[nxt[u]]) {
            if (t[2] >= B) {
                // 大周期：直接枚举
                for (int i = t[0]; i <= t[1]; i += t[2]) {
                    ans += 1ll * c[u] * s[d[u] - i];
                }
                continue;
            }

            // 小周期：使用预计算数组
            int pl = find(d[u] - t[1] - 1, dep);
            int pr = find(d[u] - t[0], dep);
            Q[len[pl]].pb({t[2], (d[u] - t[0]) % t[2], -c[u]});
            Q[len[pr]].pb({t[2], (d[u] - t[0]) % t[2], c[u]});
        }

        // 递归处理子节点
        for (int v : E[u]) {
            calc(v, dep + 1);
        }

        // 处理查询
        for (auto t : Q[u]) {
            ans += 1ll * t[2] * w[t[0]][t[1]];
        }

        // 清理临时数组
        Q[u].clear();
        s[d[u]] -= c[u];
        for (int i = 1; i < B; i++) {
            w[i][d[u] % i] -= c[u];
        }
    }

    // 主求解函数
    void solve(int op = 1) {
        getfail();
        calc(1, 1);
        Ans += 1ll * op * ans;
    }
} T;

// 寻找树的重心
void findrt(int u, int fa) {
    int mx = 0;
    sz[u] = 1;

    for (auto v : G[u]) {
        if (!vis[v[0]] && v[0] != fa) {
            findrt(v[0], u);
            sz[u] += sz[v[0]];
            mx = max(mx, sz[v[0]]);
        }
    }

    if (max(mx, tot - sz[u]) <= tot / 2) {
        rt = u;
    }
}

// DFS遍历树，构建AC自动机
void dfs(int u, int fa, int p) {
    sz[u] = 1;

    for (auto v : G[u]) {
        if (!vis[v[0]] && v[0] != fa) {
            dfs(v[0], u, T.nwnode(p, v[1]));
            sz[u] += sz[v[0]];
        }
    }
}

// 点分治主函数
void solve(int u) {
    vis[u] = 1;
    
    // 处理当前子树
    T.init();
    T.c[1]++;
    dfs(u, 0, 1);
    T.solve();

    // 去重：减去同一子树内的路径
    for (auto v : G[u]) {
        if (!vis[v[0]]) {
            T.init();
            dfs(v[0], u, T.nwnode(1, v[1]));
            T.solve(-1);
        }
    }

    // 递归处理子树
    for (auto v : G[u]) {
        if (!vis[v[0]]) {
            tot = sz[v[0]];
            findrt(v[0], u);
            solve(rt);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;

    // 预处理幂次
    T.pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        T.pw[i] = mul(T.pw[i - 1], bas);
    }

    // 读入树结构
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        G[u].pb({v, w});
        G[v].pb({u, w});
    }

    // 点分治求解
    tot = n;
    findrt(1, 0);
    solve(rt);
    
    cout << Ans << endl;
    return 0;
}

代码说明

关键数据结构

• ACAM 类：处理回文路径的核心数据结构
• G 数组：树的邻接表存储
• 哈希数组：hs[i][0] 和 hs[i][1] 分别存储正反哈希值

算法核心

1. 点分治框架

重心寻找：

void findrt(int u, int fa)

通过DFS计算子树大小，找到重心。

分治处理：

void solve(int u)

以重心为根，分别处理整棵树和各个子树，避免重复计数。

2. AC自动机与回文处理

节点创建：

int nwnode(int p, int x)

创建新节点时同时计算正反哈希值，用于判断回文性。

Fail指针构建：

void getfail()

标准的AC自动机构建过程，同时处理回文相关指针。

3. 回文路径统计

周期优化：

• 小周期（< B）：使用预计算数组 w 快速统计
• 大周期（≥ B）：直接枚举统计

二分查找：

int find(int x, int dep)

快速定位满足深度条件的节点。

数学原理

双哈希判断回文：

• 正向哈希：$h_{forward} = \sum s_i \cdot base^{n-i}$
• 反向哈希：$h_{backward} = \sum s_i \cdot base^{i-1}$
• 回文条件：$h_{forward} = h_{backward}$

Border理论： 利用回文串的周期性质，将路径按周期分类处理，提高统计效率。

复杂度分析

• 点分治：$O(n \log n)$ 层递归
• AC自动机：每层 $O(n)$ 构建和统计
• 总复杂度：$O(n \log n \cdot \text{常数})$
• 空间复杂度：$O(n)$