深入理解树链剖分（C语言实现树链剖分算法详解）

为什么需要树链剖分？

假设我们要频繁查询树上两点间路径的权值和，或者更新某条路径上的所有点权。如果每次暴力遍历路径，时间复杂度会高达 O(n)，效率极低。

而通过树上路径查询结合线段树，我们可以将单次操作优化到 O(log²n)，极大提升性能。这也是树链剖分在算法竞赛中广受欢迎的原因。

树链剖分的基本步骤

1. 第一次 DFS：计算每个节点的子树大小、深度、父节点，并确定重儿子。
2. 第二次 DFS：进行重链剖分，为每个节点分配在线段树中的位置（dfn 序）。
3. 构建线段树：根据 dfn 序建立线段树，支持区间查询/更新。
4. 路径操作：利用重链跳转，将路径拆分为若干区间，在线段树上处理。

C语言实现示例

下面是一个完整的 C 语言树链剖分模板，用于支持路径求和与单点修改。

// 树链剖分 + 线段树 模板（C语言）#include <stdio.h>#include <string.h>#define MAXN 100010int n, m, root;int head[MAXN], to[MAXN<<1], nxt[MAXN<<1], ecnt = 0;int val[MAXN]; // 节点初始权值void add_edge(int u, int v) {    to[++ecnt] = v;    nxt[ecnt] = head[u];    head[u] = ecnt;}// 第一次DFS：预处理 size, dep, fa, sonint dep[MAXN], fa[MAXN], size[MAXN], son[MAXN];void dfs1(int u, int f) {    size[u] = 1;    fa[u] = f;    dep[u] = dep[f] + 1;    son[u] = 0;    for (int i = head[u]; i; i = nxt[i]) {        int v = to[i];        if (v == f) continue;        dfs1(v, u);        size[u] += size[v];        if (size[v] > size[son[u]]) son[u] = v;    }}// 第二次DFS：剖分重链，生成dfn序int top[MAXN], dfn[MAXN], rnk[MAXN], timer = 0;void dfs2(int u, int t) {    top[u] = t;    dfn[u] = ++timer;    rnk[timer] = u;    if (!son[u]) return;    dfs2(son[u], t); // 先处理重儿子    for (int i = head[u]; i; i = nxt[i]) {        int v = to[i];        if (v == fa[u] || v == son[u]) continue;        dfs2(v, v); // 轻儿子新开一条链    }}// 线段树部分（区间求和）long long tree[MAXN << 2];void build(int p, int l, int r) {    if (l == r) {        tree[p] = val[rnk[l]];        return;    }    int mid = (l + r) >> 1;    build(p<<1, l, mid);    build(p<<1|1, mid+1, r);    tree[p] = tree[p<<1] + tree[p<<1|1];}void update(int p, int l, int r, int pos, int val) {    if (l == r) {        tree[p] = val;        return;    }    int mid = (l + r) >> 1;    if (pos <= mid) update(p<<1, l, mid, pos, val);    else update(p<<1|1, mid+1, r, pos, val);    tree[p] = tree[p<<1] + tree[p<<1|1];}long long query(int p, int l, int r, int ql, int qr) {    if (ql <= l && r <= qr) return tree[p];    int mid = (l + r) >> 1;    long long res = 0;    if (ql <= mid) res += query(p<<1, l, mid, ql, qr);    if (qr > mid) res += query(p<<1|1, mid+1, r, ql, qr);    return res;}// 查询u到v路径上的权值和long long path_query(int u, int v) {    long long res = 0;    while (top[u] != top[v]) {        if (dep[top[u]] < dep[top[v]]) {            int tmp = u; u = v; v = tmp;        }        res += query(1, 1, n, dfn[top[u]], dfn[u]);        u = fa[top[u]];    }    if (dep[u] > dep[v]) {        int tmp = u; u = v; v = tmp;    }    res += query(1, 1, n, dfn[u], dfn[v]);    return res;}int main() {    scanf("%d", &n);    for (int i = 1; i <= n; i++) scanf("%d", &val[i]);    for (int i = 1; i < n; i++) {        int u, v;        scanf("%d%d", &u, &v);        add_edge(u, v);        add_edge(v, u);    }    root = 1;    dfs1(root, 0);    dfs2(root, root);    build(1, 1, n);    // 示例：查询1到n的路径和    printf("%lld\n", path_query(1, n));    return 0;}

关键点解析

• son[u]：u 的重儿子。
• top[u]：u 所在重链的顶端节点。
• dfn[u]：u 在线段树中的下标（DFS序）。
• 路径查询时，总是让深度更大的节点向上跳，直到两点在同一重链。

总结

通过本教程，你已经掌握了C语言数据结构中一个高阶技巧——树链剖分。它将树问题转化为序列问题，配合线段树可高效解决各类树上路径查询任务。

虽然代码较长，但只要理解两次 DFS 的作用和路径跳转逻辑，就能灵活应用。建议动手实现一遍，并尝试解决如“树上路径最大值”、“子树加法”等变种问题。

希望这篇C语言树链剖分教程对你有所帮助！如果你觉得有用，欢迎分享给更多学习算法的朋友。