30 分钟吃透树链剖分从路径查询到换根的完整拆解【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki树上有 $n$ 个点带权每次询问两点之间路径的权值和暴力顺着链爬一遍要 $O(n)$。能不能压到 $O(\log^2 n)$可以这就是树链剖分重链剖分HLD要干的事把树拆成若干条重链映射到数组上交给线段树。读完这篇你能写出两遍 DFS 预处理、三个常用查询并搞懂换根时的分类讨论。一眼分清重链和轻链树剖把每条重链压成一段连续编号链内和子树的 DFS 序都是连续区间——这是后文所有查询的地基。先看几个名词全都不难重儿子一个结点的儿子中子树规模最大的那个打平随便挑一个重边结点到它重儿子的边轻边到其余儿子的边重链若干条首尾相接的重边连成的路径落单的叶子结点也算一条长度为一的重链。链和编号都备好了剩下的就交给序列上的数据结构。四条性质撑起 O(log²n)为什么路径操作能快靠的是四条性质每个结点恰好属于一条重链——树被不重不漏地切成若干链不会漏点也不会重复计数同一条重链内 DFS 序连续——一条链直接对应数组上一段区间可以整段查子树内 DFS 序也连续——子树维护白送不用额外处理任意路径经过的轻边不超过 $O(\log n)$ 条——走一条轻边所在子树规模至少砍半链的跳数天然有上界。前三条把树上操作翻译成了区间操作第四条保证翻译后只有 $O(\log n)$ 段区间$O(\log n)\times O(\log n)O(\log^2 n)$ 就这么来的。这两组信息怎么填答案就是两遍 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; // 子树最大的儿子就是重儿子 } }第二遍按重儿子优先的顺序定链顶和 DFS 序void dfs2(int u, int ftop) { top[u] ftop; // 本结点所在链的链顶 dfn[u] idx, rnk[idx] u; // 分配 DFS 序rnk 反查结点 if (son[u]) dfs2(son[u], ftop); // 重儿子继承链顶留在本链 for (auto v : G[u]) if (v ! son[u] v ! fa[u]) dfs2(v, v); // 轻儿子各自开新链 }跑完这两遍同一条链上的点 dfn 连号子树落在 $[\text{dfn}[u],\ \text{dfn}[u]\text{siz}[u]-1]$编号体系建好了该写真正的查询代码。三个操作各有一个坑先把结点权值按 dfn 灌进线段树三个常用操作如下。路径查询long long path_query(int u, int v) { long long ans 0; while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) swap(u, v); // 始终跳链顶更深的一侧 ans seg.query(dfn[top[u]], dfn[u]); // 整条链一次查完 u fa[top[u]]; // 跳到链顶的父亲 } if (dep[u] dep[v]) swap(u, v); return ans seg.query(dfn[u], dfn[v]); // 同链后补一段 }它为什么正确每次把链顶更深的整段摘掉路径只会被拆成 $O(\log n)$ 段、每段都是一次区间查询不重不漏。子树查询long long subtree_query(int u) { return seg.query(dfn[u], dfn[u] siz[u] - 1); // 子树在 DFS 序上是一段连续区间 }它为什么正确DFS 进出时间戳的常规性质子树天然占一段连续区间。LCAint 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同链后答案就在两者之间。换根要分几种情况子树查询依赖谁是根而路径查询不依赖两点间路径与根无关所以换根只需重做子树的映射。设当前根为 $rt$、查询结点为 $u$情况判定做法$u rt$相等以 $u$ 为根的子树就是整棵树直接查 $[1, n]$$u$ 是 $rt$ 在原树根固定为 1 的预处理树上的祖先$u$ 在 $1\to rt$ 路径上沿 $rt$ 所在的重链跳到 $u$ 这一层找到 $rt$ 分支上的那个儿子 $v$答案是整棵树排除$v$ 的子树即查 $[1,\text{dfn}[v)-1]$ 和 $[\text{dfn}[v]\text{siz}[v],n]$ 两段其他都不满足换根不影响 $u$ 的子树照常查 $[\text{dfn}[u],\text{dfn}[u]\text{siz}[u)-1]$第二行最容易出错$v$ 是 $u$ 到 $rt$ 路径上除 $u$ 外深度最小的点可以用在 $rt$ 的链上跳跳完同链后按 $\text{dfn}1$ 取的方式一次拿到。静态树上三个操作就绪最后一类题就是换根了。容易翻车的细节✅ 四个高频坑对号入座轻儿子必须开新链dfs2(v, v)的第二个参数是 $v$ 自己写成dfs2(v, ftop)会把整片轻子树并进父链性质 4 直接失效子树右端点是 $\text{dfn}[u]\text{siz}[u]-1$写成 $\text{dfn}[u]\text{siz}[u]$ 会多算一个不相关结点跳链后必须更新结点查询完fa[top[u]]之后忘了给 $u$ 赋值就变成死循环重边优先要排前面第二遍 DFS 先递归重儿子、再补轻儿子顺序颠倒 dfn 照样是合法 DFS 序但链就不再连号区间查询全废。性能上两条建议用全局数组静态开线段树并打懒标记比现场 new 快很多路径查询写成两端交替上跳比dep[top]大者跳代码更短、常数也稳。基础都打牢了接下来按梯度刷。按梯度刷的三条练习P3379树上求 LCA先用树剖写法实现一遍体会跳链即 LCAP3384路径修改 路径查询模板覆盖单点修改、区间加、区间求和LOJ 139带换根的子树修改/查询把上表三种情况完整写出来。卡住时直接对照官方文档 树链剖分它把换根取 $v$ 的完整推导讲得很细代码层面可以打开 hld 模板 逐行比对你的dfs2和跳链逻辑哪里对不上问题就在哪里。别急着啃换根先把 LCA 和 P3384 敲熟再说。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考