企业官网建设流程全解析

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)

为什么路径操作能快？靠的是四条性质：

1. 每个结点恰好属于一条重链——树被不重不漏地切成若干链，不会漏点也不会重复计数；
2. 同一条重链内 DFS 序连续——一条链直接对应数组上一段区间，可以整段查；
3. 子树内 DFS 序也连续——子树维护白送，不用额外处理；
4. 任意路径经过的轻边不超过 $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 进出时间戳的常规性质，子树天然占一段连续区间。

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，同链后答案就在两者之间。

换根要分几种情况

子树查询依赖"谁是根"，而路径查询不依赖（两点间路径与根无关），所以换根只需重做子树的映射。设当前根为 $rt$、查询结点为 $u$：

第二行最容易出错：$v$ 是 $u$ 到 $rt$ 路径上除 $u$ 外深度最小的点，可以用"在 $rt$ 的链上跳，跳完同链后按 $\text{dfn}+1$ 取"的方式一次拿到。静态树上三个操作就绪，最后一类题就是换根了。

容易翻车的细节

✅ 四个高频坑，对号入座：

1. 轻儿子必须开新链：dfs2(v, v)的第二个参数是 $v$ 自己，写成dfs2(v, ftop)会把整片轻子树并进父链，性质 4 直接失效；
2. 子树右端点是 $\text{dfn}[u]+\text{siz}[u]-1$：写成 $\text{dfn}[u]+\text{siz}[u]$ 会多算一个不相关结点；
3. 跳链后必须更新结点：查询完fa[top[u]]之后忘了给 $u$ 赋值，就变成死循环；
4. 重边优先要排前面：第二遍 DFS 先递归重儿子、再补轻儿子，顺序颠倒 dfn 照样是合法 DFS 序，但链就不再连号，区间查询全废。

性能上两条建议：用全局数组静态开线段树并打懒标记，比现场 new 快很多；路径查询写成两端交替上跳（比dep[top]大者跳），代码更短、常数也稳。基础都打牢了，接下来按梯度刷。

按梯度刷的三条练习

1. P3379：树上求 LCA，先用树剖写法实现一遍，体会"跳链即 LCA"；
2. P3384：路径修改 + 路径查询模板，覆盖单点修改、区间加、区间求和；
3. LOJ 139：带换根的子树修改/查询，把上表三种情况完整写出来。

卡住时直接对照官方文档 树链剖分，它把换根取 $v$ 的完整推导讲得很细；代码层面可以打开 hld 模板 逐行比对你的dfs2和跳链逻辑，哪里对不上问题就在哪里。

别急着啃换根，先把 LCA 和 P3384 敲熟再说。

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