树链剖分（HLD）是省选必考算法，本文详解 2026 最新版。
树链剖分解决什么问题
- 树上路径查询
- 树上路径修改
- 子树查询 / 修改
核心概念
- 重儿子：子树最大的儿子
- 轻儿子：非重儿子
- 重链：从根到重儿子的链
- dfs 序：树链剖分的编号
两个 dfs
dfs1：求子树大小和重儿子
dfs2：剖分树链，分配 dfs 序
经典应用
- LCA（最近公共祖先）
- 树上路径和
- 树上路径最大值
- 子树和
2026 新增考点
- 树上启发式合并（DSU on tree）
- 长链剖分
- 点分治 + 树链剖分
省选一对一辅导：151 6522 2880