树链剖分：把树上的路径查询压到 O(log²n)，顺手支持换根

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

树上任意两点之间查路径权值和，暴力每次把路径走一遍是 O(n)，10^5 个点 10^5 次询问直接爆炸。树链剖分（通常指重链剖分，HLD）把整棵树切成若干条重链，让任意路径变成 O(log n) 段连续区间，配上线段树，一次查询 O(log²n)。这篇讲透：树怎么剖、两次 DFS 各跑什么、路径查询、子树查询、LCA 和换根四类操作怎么写，以及每一步最容易踩的坑。

核心思想：把树切成几条主干链

先定义几个词。对每个结点，看它的子结点：子树最大的那个叫重子结点，人话就是"人最多的分叉，跟着它走"。结点到重子结点的边叫重边；通向其他子结点的边叫轻边，人话就是"岔路，走进去能到的子树规模至少砍半"。重边首尾相接构成重链，孤立的结点也算长度 1 的链。

为什么链"少"？核心性质：从根到任意结点，轻边数量不超过 O(log n)。直觉推导：每向下跨一条轻边，孩子的子树规模至多是父亲的一半（否则它就该是重子结点）。子树规模每跨一条轻边至少减半，从 n 减到 1 最多 log n 次，所以轻边数被 log n 封死。重链正是被轻边隔开的，于是一条任意路径最多拆成 O(log n) 条链——这是树链剖分所有效率结论的源头。

两次 DFS 分别跑什么

剖分用两趟 DFS 完成。第一趟自底向上收基础信息：父亲、深度、子树大小，并确定谁是重子结点。

void dfs1(int u, int f) { fa[u] = f; dep[u] = dep[f] + 1; siz[u] = 1; for (int v : G[u]) { if (v == f) continue; // 不折返进父亲 dfs1(v, u); siz[u] += siz[v]; // 子树最大的孩子记为重子结点，并列时任取其一 if (siz[v] > siz[son[u]]) son[u] = v; } }

最容易漏的细节：son[u]要初始化为 0 且保证siz[0] == 0，否则叶子结点比较时会挑出一个不存在的"重孩子"。

第二趟自顶向下，给每个结点定链顶、DFS 序和逆映射。

void dfs2(int u, int tp) { top[u] = tp; dfn[u] = ++tot; // DFS 序即线段树里的编号 rnk[tot] = u; if (son[u]) dfs2(son[u], tp); // 先递归重儿子，保住重链的 DFS 序连续 for (int v : G[u]) if (v != fa[u] && v != son[u]) dfs2(v, v); // 轻孩子自成一条新链 }

为什么必须先递归重儿子：只有这样，同一重链上的结点才会拿到挨着的 DFS 序号，整条链对应线段树里的一个区间；谁先谁后错了，链就被劈开，后面所有区间操作全部作废。

路径查询模板怎么套

HLD 路径查询的骨架一句话："两点不在同一条链？跳链顶更深的那条，把整链区间查完，结点挪到链顶上方；直到同链，补齐最后一段。"

long long path_query(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.query(dfn[top[u]], dfn[u]); u = fa[top[u]]; // 整条链处理完，跳到链顶之上的链 } if (dep[u] > dep[v]) swap(u, v); res += seg.query(dfn[u], dfn[v]); return res; }

最容易写错：swap 的依据是链顶的深度，不是结点自身深度——结点浅不代表它的链顶浅。复杂度：循环每轮跨掉一条轻边，至多 O(log n) 轮，每轮线段树查询 O(log n)，合计 O(log²n)。路径修改是同一个骨架，把 query 换成 add 即可。

子树查询用 DFS 序区间拿

子树操作其实不依赖剖分本身，吃的是"子树 DFS 序连续"这个性质：u 的子树就是闭区间 [dfn[u], dfn[u] + siz[u] - 1]。

long long subtree_query(int u) { return seg.query(dfn[u], dfn[u] + siz[u] - 1); }

一行收工。最容易写错：区间是闭区间，siz[u] - 1少一个减号就多出半个子树；另外这个区间只对固定根成立，一旦换根立刻失效——放到最后单独讲。

LCA：跳链的顺手副产品

LCA 不需要线段树，复用跳链循环就行：谁的链顶深就跳谁，跳进同一条链后，深度浅的那个就是答案。

int lca(int u, int v) { while (top[u] != top[v]) { if (dep[top[u]] > dep[top[v]]) u = fa[top[u]]; else v = fa[top[v]]; } return dep[u] < dep[v] ? u : v; // 同链：LCA 是浅的那个 }

最容易写错：跳出循环后两点已在同一条重链上，这时再fa[u]一步就跳过了真正的 LCA。

换根时三种情况怎么分

根会换，但预处理不能重跑——DFS 序和重链保持静止，"当前树"上的操作映射回"原始树"的区间来落。路径查询不受换根影响（两点简单路径唯一），直接套模板。子树操作才是重灾区：以 u 为中心的子树操作，看 u 和当前根 root 的位置关系，只有三种情况。

情况一：u 就是新根

u 的"子树"就是整棵树，对线段树整体加 / 整体查，别绕任何弯。

情况二：u 是新根在原始树上的祖先

最容易错。换根后 u 的"子树"变成"整棵树挖掉某个 v 的原始子树"，v 是 u 到 root 原始路径上 u 的下一个孩子。v 的求法是"跳链逼近 + 链内定位"两步：

int find_child(int u) { int v = root; while (dep[top[v]] > dep[u] + 1) v = fa[top[v]]; // 跳到与 u 相邻的链 // 统一式：同时覆盖 v 是 u 的轻儿子、与 u 同重链两种形态 return rnk[dfn[top[v]] + dep[u] + 1 - dep[top[v]]]; }

为什么这个式子看着唬人其实很直白：跳完循环后，v 所在链的链顶深度要么是 dep[u]+1（v 是 u 的轻儿子），要么不超过 dep[u]（v 与 u 同链）。两种形态下目标都在该链上深度 dep[u]+1 的位置，而同链 DFS 序连续，"链顶编号 + 深度差"一行算术就出编号，再经 rnk 换回结点。

然后操作落在两段区间：

int v = find_child(u); seg.add(1, dfn[v] - 1, w); // v 子树之前的所有结点 seg.add(dfn[v] + siz[v], n, w); // v 子树之后的所有结点

情况三：其余情形

u 和新根不在同一支，或者 u 本就在 root 的原始子树里。此时当前树的 u 子树与原始树完全一致，按 [dfn[u], dfn[u] + siz[u] - 1] 正常操作即可。

练习路线

• 入门：洛谷 P3379 最近公共祖先。不写线段树，只写两次 DFS 加跳链，验证自己的剖分信息是否正确。
• 进阶：洛谷 P3384 重链剖分模板。单点改 + 路径求和求极值，线段树要自己实现。
• 综合：LOJ 139 树链剖分。换根 + 路径 / 子树增删改查，上面三种情况全部登场。

延伸阅读：hld 实现文档、换根参考代码 hld_4.cpp。

读完这篇文章，你应该能独立做完三件事：默写两次 DFS，并解释"重儿子优先递归"为什么不可调换；给任意一棵树指出哪些是轻边，并估出某条路径会拆成几条重链；在带换根的树上，把任意一次子树操作映射成原始树上的区间操作。

找一道带换根的题手撕一遍，比再读三篇博客管用。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki