C++树链剖分完全指南（从零开始掌握树上路径高效查询与更新）

二、关键概念解析

• 重儿子（Heavy Child）：对于一个非叶子节点 u，其子树大小最大的那个子节点称为重儿子。
• 轻儿子（Light Child）：除重儿子外的其他子节点。
• 重链（Heavy Chain）：由若干个通过重边连接的节点组成的链。每条重链的顶端称为“链顶”（top）。
• DFS序（dfn）：通过特定顺序的 DFS 遍历，为每个节点分配一个在线性数组中的位置，保证每条重链上的节点在数组中连续。

通过这种划分，任意两点 u 和 v 之间的路径可以被拆分为若干段，每一段都是某条重链的连续子区间。这正是我们能使用线段树处理的关键！

三、实现步骤详解

树链剖分通常需要两次 DFS：

1. 第一次 DFS：计算每个节点的父节点（fa）、深度（dep）、子树大小（size）和重儿子（son）。
2. 第二次 DFS：分配 DFS 序（dfn），记录链顶（top），并构建用于线段树的线性数组（a[]）。

1. 第一次 DFS 代码

void dfs1(int u, int father) {    fa[u] = father;    dep[u] = dep[father] + 1;    size[u] = 1;    son[u] = -1; // 初始化无重儿子    for (int v : adj[u]) {        if (v == father) continue;        dfs1(v, u);        size[u] += size[v];        if (son[u] == -1 || size[v] > size[son[u]])            son[u] = v; // 更新重儿子    }}

2. 第二次 DFS 代码

int cnt = 0; // 全局 dfn 计数器void dfs2(int u, int t) {    top[u] = t;    dfn[u] = ++cnt;    a[cnt] = val[u]; // val[u] 是原树中 u 的点权    if (son[u] != -1)        dfs2(son[u], t); // 优先遍历重儿子，保持链连续    for (int v : adj[u]) {        if (v == fa[u] || v == son[u]) continue;        dfs2(v, v); // 轻儿子新开一条链    }}

四、路径操作：如何查询/修改 u 到 v 的路径？

核心思想：不断将 u 和 v 所在链中较深的那个跳到其链顶的父节点，同时处理当前链段。

void update_path(int u, int v, int delta) {    while (top[u] != top[v]) {        if (dep[top[u]] < dep[top[v]]) swap(u, v);        seg_tree.update(dfn[top[u]], dfn[u], delta); // 线段树区间更新        u = fa[top[u]];    }    if (dep[u] > dep[v]) swap(u, v);    seg_tree.update(dfn[u], dfn[v], delta);}long long query_path(int u, int v) {    long long res = 0;    while (top[u] != top[v]) {        if (dep[top[u]] < dep[top[v]]) swap(u, v);        res += seg_tree.query(dfn[top[u]], dfn[u]);        u = fa[top[u]];    }    if (dep[u] > dep[v]) swap(u, v);    res += seg_tree.query(dfn[u], dfn[v]);    return res;}

五、完整初始化流程

int main() {    // 输入建图...    dfs1(1, 0);      // 以1为根    dfs2(1, 1);    seg_tree.build(1, 1, n); // 用 a[1..n] 构建线段树    // 处理查询/更新...    return 0;}

六、总结

树链剖分是C++图论算法中处理树上路径问题的利器。虽然代码较长，但只要理解了“重链”和“DFS序”的思想，就能轻松掌握。它常用于解决以下问题：

• 路径求和 / 最大值 / 最小值
• 路径加法 / 赋值更新
• 子树操作（子树在线段树中是连续区间）

通过本教程，相信你已经对树链剖分算法详解有了清晰的认识。记住：树链剖分的本质是“树转序列”，再用数据结构维护序列。多练习几道题（如洛谷 P3384），你就能熟练运用这一强大工具！

关键词回顾：C++树链剖分、树链剖分算法详解、树上路径查询、C++图论算法。