树上基础题单

树链剖分之前，至少要能熟练处理父子关系、深度、子树大小、DFS 序和 LCA。树上问题先问“这是子树信息还是路径信息”，再决定使用哪种工具。

一、树的表示与遍历

先把边表、根、父亲、深度和遍历顺序写清楚。二叉树题是理解递归结构的好入口。

• luogu P1305 新二叉树题解
  · P1305 新二叉树
• luogu P1030 [NOIP 2001 普及组] 求先序排列题解
  · P1030 求先序排列
• luogu P1229 遍历问题题解
  · P1229 遍历问题
• codeforces 115A未收录
  · Codeforces 115A Party
• codeforces 580C未收录
  · Codeforces 580C Kefa and Park

二、树形 DP 与子树信息

树形 DP 通常是“先递归处理孩子，再由孩子状态合并父亲状态”。要明确状态是否允许选择当前节点，以及父子之间的限制。

• luogu P1122 最大子树和题解
  · P1122 最大子树和
• luogu P1352 没有上司的舞会题解
  · P1352 没有上司的舞会
• luogu P2015 二叉苹果树题解
  · P2015 二叉苹果树
• luogu P2986 [USACO10MAR] Great Cow Gathering G题解
  · P2986 Great Cow Gathering G
• luogu P3478 [POI 2008] STA-Station题解
  · P3478 STA-Station

三、LCA 与倍增

LCA 是树上路径问题的共同前置。先理解朴素向上跳，再用倍增把跳跃过程压到对数复杂度。

• luogu P3379 【模板】最近公共祖先（LCA）题解
  · P3379 【模板】最近公共祖先（LCA）
• atcoder ABC070D未收录
  · AtCoder ABC070 D Transit Tree Path
• luogu P4427 [BJOI2018] 求和题解
  · P4427 求和

四、树上差分与路径统计

路径加、路径计数不一定要马上上树链剖分。先用 LCA 和差分把所有路径贡献汇总到节点，再做一次自底向上的统计。

• luogu P3258 [JLOI2014] 松鼠的新家题解
  · P3258 松鼠的新家
• luogu P3128 [USACO15DEC] Max Flow P题解
  · P3128 Max Flow P
• luogu P4211洛谷原题
  · P4211 LCA

过关标准

进入树链剖分前，应能独立解释：

1
2
3
4dfs 序为什么能把子树变成连续区间：
LCA 如何把路径拆成两条向上的链：
树上差分在路径端点处为什么这样加减：
树形 DP 为什么可以后序合并：