树链剖分介绍
树链剖分是什么？主要用来处理什么问题
树链剖分（Heavy-Light Decomposition, HLD）。
1. 树链剖分的定义
树链剖分是一种 把树分解成若干条链 的算法技巧。
在一棵树上，我们把每个节点的“重儿子”挑出来（通常是子树规模最大的儿子），把它和父亲连成 重边，其它边就是 轻边。
这样整棵树就被拆分成若干条 重链，并且有一个关键性质：
- 从根到任意一个节点的路径上，**轻边的数量至多是 \(O(\log n)\) **。
因此，任何树上的一条路径，都可以用 若干条（ \(\log n\) 级别）连续的链 来表示。
2. 树链剖分的主要用途
它的核心目标是把 树上的路径/子树问题 转化为 线段树/树状数组上的区间问题，从而可以在 \(O(\log^2 n)\) 的时间里解决很多复杂问题。
常见应用有：
- 路径查询
- 比如：查询树上两点路径上的最大值、最小值、和、异或值……
- 利用树链剖分把路径分解成若干段连续区间，用线段树维护。
- 路径修改
- 比如：把树上某条路径上的点权/边权全部加上一个数。
- 仍然是拆成若干区间，交给线段树做区间修改。
- 子树查询 / 修改
- 如果我们按照 DFS 序（欧拉序）编号，每个子树对应一个连续区间。
- 可以直接用线段树维护子树问题。
- 更复杂的树上问题
- 树上差分、树上 DP 的优化。
- 结合树剖 + 数据结构，可以处理动态树上的很多操作。
树链剖分前置知识是什么
学 树链剖分（HLD） 之前，最好先掌握一些 图论 + 数据结构的基础知识，这样学习起来会轻松很多。
我给你分几个层次讲：
1. 树的基本知识 🌳
树链剖分是树上的高级技巧，所以树的基础必须牢固。
需要掌握的内容有：
- DFS遍历
- 如何用 DFS 遍历树，记录进入时间 / 退出时间（欧拉序）。
- 子树大小
- 会写
dfs(u)统计每个节点子树大小。
- 会写
- 父亲与深度
- 在 DFS 时记录
fa[u]（父亲节点）和dep[u]（深度）。
- 在 DFS 时记录
👉 这些是后续判断“重儿子”和路径分解的核心。
2. 最近公共祖先 LCA
为什么要学 LCA？
- 树链剖分常常需要把路径 \((u,v)\) 拆解成 \((u,LCA(u,v))\) 和 \((v,LCA(u,v))\) 。
- 当然，在 HLD 里，LCA 也能用树剖自带的
top[]数组来求，但原理和 LCA 高度相关。
所以至少要会：
- 倍增法 LCA （
O(log n)查询）。 - 或 Tarjan 离线 LCA。
3. 数据结构：线段树 / 树状数组
树链剖分的最终目标是 把树上路径/子树问题转化为区间问题。
所以你必须熟悉：
- 线段树：区间修改、区间查询。
- 懒标记：比如区间加法、区间乘法、区间取最大值等。
如果连线段树都不会写，HLD 基本没法落地。
4. DFS 序（欧拉序）与子树映射
你需要理解：
- 在 DFS 时给每个节点一个时间戳
dfn[u]。 - 子树的所有节点编号是 一段连续区间。
- 例如，
[dfn[u], dfn[u] + size[u] - 1]对应u的整棵子树。
- 例如，
- 这是处理 子树查询/修改 的关键。
5. 树剖专属概念
等你有了以上基础，就能自然地理解树剖里的几个数组：
son[u]：重儿子（子树最大）top[u]：当前重链的链顶dfn[u]：DFS 序编号rk[pos]：DFS 序对应的节点fa[u], dep[u], siz[u]：父亲、深度、子树大小
这些概念本质上都是 DFS + 子树大小 的应用。
✅ 总结
树链剖分的前置知识：
- 树的基本 DFS（父亲、深度、子树大小）
- 最近公共祖先（LCA） 的思想
- 线段树/树状数组（区间修改 + 区间查询）
- DFS 序与子树映射
- 熟悉 基本图论建图（邻接表存树，dfs 遍历）