树链剖分把树上的路径查询压到 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]1v 是 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考