树链剖分落地手册两次 DFS 三个模板 换根全解【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki树上路径查询还在 O(n) 暴力枚举重链剖分把它压到 O(log²n)。把任意路径拆成 O(log n) 条 DFS 序连续的链段交给线段树收尾即可。这篇按「拆链 → 模板 → 换根」的顺序把树链剖分一次讲透。一张图看懂重链与轻链 图一棵树的重链剖分——灰色为子树规模大的重子结点粗黑边是重边细边是轻边绿色框出的连通块即重链每个结点的「重子结点」是子树规模最大siz 最大的那个儿子它和父亲之间是重边其余儿子是轻子结点对应轻边。重边首尾相连把整棵树划成若干条重链每个结点恰好落在一条链上落单的结点也算一条链。剖分后按 DFS 序输出同一条重链上的结点 dfn 必然连续——这是后面所有区间操作的依据。沿任意一条轻边往下走子树规模至少砍半所以一条路径上的重链段数不超过 O(log n)路径查询的复杂度上限由此而来。两次 DFS 剖分流程有了定义剖分本身并不复杂两趟 DFS一趟算规模一趟定链顶和编号。第一遍 DFS算子树规模、定重儿子void dfs1(int u, int f) { fa[u] f, dep[u] dep[f] 1, siz[u] 1; for (auto v : G[u]) { if (v f) continue; dfs1(v, u); siz[u] siz[v]; if (siz[v] siz[son[u]]) son[u] v; // 子树最大的儿子 } }后序处理子树回溯后累加 siz顺手记下最大的儿子。一趟搞定父结点、深度、子树规模、重儿子四样东西。第二遍 DFS定链顶、压 DFS 序void dfs2(int u, int ftop) { top[u] ftop, dfn[u] idx, rnk[idx] u; if (son[u]) dfs2(son[u], ftop); // 重儿子续链链顶不变 for (auto v : G[u]) if (v ! son[u] v ! fa[u]) dfs2(v, v); // 轻儿子起新链 }从根出发重边优先递归重儿子继承链顶继续往下压 dfn轻儿子各自当新链起点。这样每条重链在 dfn 上就是一段连续区间子树也天然连续。预处理到此为止剩下的全是「区间问题」。三个高频模板路径 / 子树 / LCA预处理完成后配合任意支持区间修改与区间查询的数据结构记作seg三个模板直接复用。路径查询模板场景求 u 到 v 路径上权值和或最大值把sum换成max即可。int query_path(int u, int v) { int res 0; while (top[u] ! top[v]) { // 不同链跳较深的链 if (dep[top[u]] dep[top[v]]) swap(u, v); res seg.sum(dfn[top[u]], dfn[u]); // 整段链是一次区间查询 u fa[top[u]]; } if (dep[u] dep[v]) swap(u, v); res seg.sum(dfn[u], dfn[v]); // 同一链上补最后一段 return res; }跳链次数 O(log n)每段再吃一个 O(log n)总复杂度 O(log² n)路径上的最大值、异或等可合并信息同理。子树查询模板场景把 u 的子树整体加一个值或查询子树权值和。// 子树 dfn 上的一段连续区间 seg.update(dfn[u], dfn[u] siz[u] - 1, w); // 子树加 int res seg.sum(dfn[u], dfn[u] siz[u] - 1); // 子树求和不需要任何树剖技巧普通 DFS 序就保证子树连续这里只是复用同一个数据结构。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 }跳链逻辑和路径查询完全同构单次 O(log n)常数比倍增还小。换根三种情况路径查询不受换根影响两点间的简单路径唯一麻烦都在子树操作上换根后的「u 的子树」在原始根比如 1的 DFS 序下可能不是一段连续区间得映射回原始树。按 u 和当前根 root 的位置关系分三种。图子树操作在序上被划分成若干连续区间的示意——换根后「排除某棵子树」正好对应区间 [1, dfn(v)) 与 [dfn(v)siz(v), n] 两段u 就是 root操作对象是整棵树直接对区间 [1, n] 下手。u 是 root 在原始树上的祖先记 v 为 u→root 路径上除 u 外的最浅结点当前树上「u 的子树」 整棵树 − v 的子树。v 从 root 出发沿重链往上跳直到dep(top[v]) dep[u]1再令v rnk[dfn[top[v]] dep[u] 1 - dep[top[v]]]随后分别操作[1, dfn[v])和[dfn[v]siz[v], n]两段即可。其他情况换根对 u 的子树无影响照常用[dfn[u], dfn[u]siz[u]-1]做。第 2 种情况是树链剖分换根的考点跳链找 v 的写法建议对着官方模板逐行读一遍。细节与性能 ⚡底层容器要区间加/区间和、极值就上线段树树状数组只够覆盖前缀可合并的场景别硬套。重链长度可整体预存给长链剖分继承 DP 数组时按链统一分配内存省掉大量零散分配。跳链循环本身很轻主要成本在线段树上常数敏感时把top/dep/dfn合并进同一层数组访问比抠位运算划算。延伸练习「洛谷 P3384」重链剖分模板区间加 路径/子树查询重链剖分模板的标配套路「LOJ 139 树链剖分」换根 路径 子树全家桶对应本文换根三种情况「洛谷 P3379」LCA只用跳链不挂数据结构专练树链剖分求 LCA模板代码与逐行讲解见 docs/graph/hld.md完整参考实现见 docs/graph/code/hld/hld_1.cpp 与 docs/graph/code/hld/hld_4.cpp。轻边减半就是树链剖分全部的秘密。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考