2026 年省选专题系列一：树链剖分。
解决什么问题
- 树上路径查询
- 树上路径修改
- 子树查询 / 修改
核心概念
- 重儿子：子树最大的儿子
- 轻儿子：非重儿子
- 重链：从根到重儿子的链
- dfs 序：树链剖分的编号
两个 dfs
- dfs1：求子树大小和重儿子
- dfs2：剖分树链，分配 dfs 序
核心操作
- LCA（最近公共祖先）
- 路径查询：跳链 + 线段树
- 子树查询：dfs 序区间
经典题型
- 树上路径和
- 树上路径最大值
- 子树和
- LCA 查询
学习建议
- 先掌握 LCA
- 再学路径查询
- 配合线段树使用
省选一对一辅导：151 6522 2880