0x2 树形dp
题单介绍
[这个题单](https://www.luogu.com.cn/training/1435)的子题单
### 0x2 树形dp
NOIp/csp 常考类型，最重要的dp
这部分的子题单：[「0x2 树形dp」](https://www.luogu.com.cn/training/13994)
#### 0x20 基础的树dp
没什么难度，入门级别的题目
[P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352) 最大权独立集问题
[P2016 战略游戏](https://www.luogu.com.cn/problem/P2016) 最小权覆盖集问题
---
#### 0x21 树上背包
有依赖性的背包
[P2014 [CTSC1997]选课](https://www.luogu.com.cn/problem/P2014) 树上背包模板
[P1273 有线电视网](https://www.luogu.com.cn/problem/P1273) 树上背包经典题
[P1272 重建道路](https://www.luogu.com.cn/problem/P1272) 类似树上背包的树形dp
[P3354 [IOI2005]Riv 河流](https://www.luogu.com.cn/problem/P3354) 树上背包，也有更快的wqs二分做法
---
#### 0x22 二次扫描法
也叫换根dp，一般第一次扫描考虑子树内的贡献，第二次扫描考虑子树外/全局的贡献
[P3478 [POI2008]STA-Station](https://www.luogu.com.cn/problem/P3478) 换根dp模板题
[P2986 [USACO10MAR]Great Cow Gathering G](https://www.luogu.com.cn/problem/P2986) 换根dp模板题
[P3047 [USACO12FEB]Nearby Cows G](https://www.luogu.com.cn/problem/P3047) 换根dp，也有其他的方法
[CF708C Centroids](https://www.luogu.com.cn/problem/CF708C) 换根dp好题
[P6419 [COCI 2015]Kamp](https://www.luogu.com.cn/problem/P6419) 分类讨论较麻烦的换根dp（听说被lswn分类3种吊打了/youl）
[P3647 [APIO2014]连珠线](https://www.luogu.com.cn/problem/P3647) 比较困难的换根dp
---
#### 0x23 基环树
$n$ 条边 $n$ 个点，突破口就在环上
[P1453 城市环路](https://www.luogu.com.cn/problem/P1453) 基环树上最大权独立集问题
[P4381 [IOI2008]Island](https://www.luogu.com.cn/problem/P4381) 基环树直径问题
---
#### 0x24 虚树
多次询问询问，总点数不多时可以去掉一些无用的点把时间复杂度优化到 $\Theta(n\log n)$
[P2495 [SDOI2011]消耗战](https://www.luogu.com.cn/problem/P2495) 虚树dp模板题
[P3233 [HNOI2014]世界树](https://www.luogu.com.cn/problem/P3233) 虚树dp比较难的题
---
#### 0x25 长链剖分
当 dp 状态只和深度有关的时候可以通过长链剖分优化到均摊 $\Theta (1)$ 的复杂度
[CF1009F Dominant Indices](https://www.luogu.com.cn/problem/CF1009F) 长链剖分模板
[P5904 [POI2014]HOT-Hotels 加强版](https://www.luogu.com.cn/problem/P5904) 神仙 dp+长链剖分优化
[P4292 [WC2010]重建计划](https://www.luogu.com.cn/problem/P4292) 01 分数规划+线段树维护长链剖分
---
#### 0x26 树形dp综合练习-part1
比较简单基础的题
[P3174 [HAOI2009]毛毛虫](https://www.luogu.com.cn/problem/P3174)
[P3554 [POI2013]LUK-Triumphal arch](https://www.luogu.com.cn/problem/P3554)
[CF219D Choosing Capital for Treeland](https://www.luogu.com.cn/problem/CF219D)
[P1131 [ZJOI2007]时态同步](https://www.luogu.com.cn/problem/P1131)
[P2052 [NOI2011]道路修建](https://www.luogu.com.cn/problem/P2052)
[P5658 括号树](https://www.luogu.com.cn/problem/P5658)
---
#### 0x27 树形dp综合练习-part2
稍微难一点的树dp
[P4253 [SCOI2015]小凸玩密室](https://www.luogu.com.cn/problem/P4253)
[P4516 [JSOI2018]潜入行动](https://www.luogu.com.cn/problem/P4516)
[CF512D Fox And Travelling](https://www.luogu.com.cn/problem/CF512D)
[CF543D Road Improvement](https://www.luogu.com.cn/problem/CF543D)
[CF1146F Leaf Partition](https://www.luogu.com.cn/problem/CF1146F)
[CF1016F Road Projects](https://www.luogu.com.cn/problem/CF1016F)
[CF671D Roads in Yusland](https://www.luogu.com.cn/problem/CF671D)