树形DP

树形$DP$ [树形dp学习笔记](https://www.luogu.com.cn/blog/BreakPlus/dp-on-tree) [[学习笔记]换根dp](https://www.luogu.com.cn/blog/sflsrick/note-how-to-change-root) [树形DP --算法竞赛专题解析（17）](https://blog.csdn.net/weixin_43914593/article/details/107145592) 注意：粗体为较为经典的题目 - [P1122 最大子树和](https://www.luogu.com.cn/problem/P1122) - [**P1352 没有上司的舞会**](https://www.luogu.com.cn/problem/P1352)：树形dp入门题 - [P2015 二叉苹果树](https://www.luogu.com.cn/problem/P2015)：一道较为经典的树形dp - [P2014 [CTSC1997]选课](https://www.luogu.com.cn/problem/P2014) - [**P2016 战略游戏**](https://www.luogu.com.cn/problem/P2016)：经典树形dp题 - [**P3478 [POI2008]STA-Station**](https://www.luogu.com.cn/problem/P3478)：换根dp入门题 - [P1040 加分二叉树](https://www.luogu.com.cn/problem/P1040) - [CF219D Choosing Capital for Treeland](https://www.luogu.com.cn/problem/CF219D) - [P1270 “访问”美术馆](https://www.luogu.com.cn/problem/P1270) - [**P1131 [ZJOI2007]时态同步**](https://www.luogu.com.cn/problem/P1131)：经典树形dp题 - [**P2279 [HNOI2003]消防局的设立**](https://www.luogu.com.cn/problem/P2279)：经典树形dp题，可以用来学习设dp状态 - [**P1273 有线电视网**](https://www.luogu.com.cn/problem/P1273)：树形背包入门题 - [P2899 [USACO08JAN]Cell Phone Network G](https://www.luogu.com.cn/problem/P2899) - [P4084 [USACO17DEC]Barn Painting G](https://www.luogu.com.cn/problem/P4084) - [**P2986 [USACO10MAR]Great Cow Gathering G**](https://www.luogu.com.cn/problem/P2986)：换根dp入门题 - [P4438 [HNOI/AHOI2018]道路](https://www.luogu.com.cn/problem/P4438)：题面杀（ - [**P3047 [USACO12FEB]Nearby Cows G**](https://www.luogu.com.cn/problem/P3047)：换根dp经典题 - [**P2585 [ZJOI2006]三色二叉树**](https://www.luogu.com.cn/problem/P2585)：经典树形dp - [P2458 [SDOI2006]保安站岗](https://www.luogu.com.cn/problem/P2458) - [UVA1218 完美的服务 Perfect Service](https://www.luogu.com.cn/problem/UVA1218) - [P1272 重建道路](https://www.luogu.com.cn/problem/P1272) - [P3177 [HAOI2015]树上染色](https://www.luogu.com.cn/problem/P3177) - [P3174 [HAOI2009]毛毛虫](https://www.luogu.com.cn/problem/P3174) - [P6554 Promises I Can't Keep](https://www.luogu.com.cn/problem/P6554) - [CF461B Appleman and Tree](https://www.luogu.com.cn/problem/CF461B) - [**CF1187E Tree Painting**](https://www.luogu.com.cn/problem/CF1187E)：换根dp经典题 - [**CF708C Centroids**](https://www.luogu.com.cn/problem/CF708C)：换根dp经典题 - [**P1453 城市环路**](https://www.luogu.com.cn/problem/P1453)：基环树dp经典题 - [**P4381 [IOI2008]Island**](https://www.luogu.com.cn/problem/P4381)：较难的基环树dp - [P3647 [APIO2014]连珠线](https://www.luogu.com.cn/problem/P3647) - [P3523 [POI2011]DYN-Dynamite](https://www.luogu.com.cn/problem/P3523) - [P3554 [POI2013]LUK-Triumphal arch](https://www.luogu.com.cn/problem/P3554) - [**P2607 [ZJOI2008]骑士**](https://www.luogu.com.cn/problem/P2607)：基环树dp - [P3565 [POI2014]HOT-Hotels](https://www.luogu.com.cn/problem/P3565) - [P3574 [POI2014]FAR-FarmCraft](https://www.luogu.com.cn/problem/P3574) - [P3576 [POI2014]MRO-Ant colony](https://www.luogu.com.cn/problem/P3576) - [P4099 [HEOI2013]SAO ](https://www.luogu.com.cn/problem/P4099) - [P3757 [CQOI2017]老C的键盘](https://www.luogu.com.cn/problem/P3757) - [P4253 [SCOI2015]小凸玩密室](https://www.luogu.com.cn/problem/P4253) - [P6213 「SWTR-04」Collecting Coins](https://www.luogu.com.cn/problem/P6213) - [**P6419 [COCI2014-2015#1] Kamp**](https://www.luogu.com.cn/problem/P6419)：换根dp经典题 - [P3267 [JLOI2016/SHOI2016]侦察守卫](https://www.luogu.com.cn/problem/P3267) - [P3354 [IOI2005]Riv 河流](https://www.luogu.com.cn/problem/P3354) - [P3237 [HNOI2014]米特运输](https://www.luogu.com.cn/problem/P3237)：树形dp结合哈希 - [P2491 [SDOI2011]消防](https://www.luogu.com.cn/problem/P2491) - [CF1120D Power Tree](https://www.luogu.com.cn/problem/CF1120D) - [CF23E Tree](https://www.luogu.com.cn/problem/CF23E) - [CF767C Garland](https://www.luogu.com.cn/problem/CF767C) - [CF581F Zublicanes and Mumocrates](https://www.luogu.com.cn/problem/CF581F) - [CF337D Book of Evil](https://www.luogu.com.cn/problem/CF337D) - [CF1153D Serval and Rooted Tree](https://www.luogu.com.cn/problem/CF1153D) - [P4629 [SHOI2015]聚变反应炉](https://www.luogu.com.cn/problem/P4629) - [P4516 [JSOI2018]潜入行动](https://www.luogu.com.cn/problem/P4516)：较难的树形背包 - [P3408 恋爱](https://www.luogu.com.cn/problem/P3408)=[UVA12186 工人的请愿书 Another Crisis](https://www.luogu.com.cn/problem/UVA12186) - [UVA1220 Hali-Bula的晚会 Party at Hali-Bula](https://www.luogu.com.cn/problem/UVA1220) - [CF1276D Tree Elimination](https://www.luogu.com.cn/problem/CF1276D) - [CF762F Tree nesting](https://www.luogu.com.cn/problem/CF762F) - [CF1082F Speed Dial](https://www.luogu.com.cn/problem/CF1082F) #### 二次扫描法 也叫换根dp，一般第一次扫描考虑子树内的贡献，第二次扫描考虑子树外/全局的贡献 - 先以1为根结点，求出$F_u$表示$u$子树的最优解 - 考虑将根结点换到1的邻点2上，只有1和2两个结点的相对关系发生变化，快速地计算出新的$F_1$和$F_2$ - 继续换根直到尝试过以每个点为根结点 - 回溯操作就是递归操作的逆 [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 --- #### 基环树 $n$ 条边 $n$ 个点，突破口就在环上 [P1453 城市环路](https://www.luogu.com.cn/problem/P1453) 基环树上最大权独立集问题 [P4381 [IOI2008]Island](https://www.luogu.com.cn/problem/P4381) 基环树直径问题 #### 树形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) --- #### 树形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)