树形DP总结
动态规划-树形类-总结
树形类的题，一般都需要用到子树的信息。
树形 DP 分为两类，一类是换根，一类是状态表示的是一棵子树的信息。
换根
母题1：
考虑先求一个点的答案，然后对于向它的孩子进发，那么到它的孩子子树变近，其余变远。
考虑方式：父亲与孩子的变化。
变式：
本题需要用到正难则反的思想，求直的情况，发现只要求出树上两两路径总和，在经过几步组合数变换即可。可以用母题的方法除二直接求解。
子树信息
母题:
考虑令 \(f[i][0/1]\) 表示对于 \(i\) 不选/选，子树 \(i\) 的答案。
若选，那么子节点都不选。
若不选，子节点无所谓，取选/不选较大值。
变式
状态同上，表示的是从 \(i\) 到其父亲的边选择情况，且答案不包括那条边。关键在于转移。
首先发现若为 \(f[i][0]\)，那么其子节点都可不选，然后我们可以贪心的替换成选的。若是 \(f[i][1]\) 少一个（若度为0答案标记为不存在）。
贪心替换需要从大到小排序，或者找第 \(k\) 个数。
需要用到快速排序/快速选择算法。
基环树
严格上不能算，但是需要先用树形 DP，然后再对环上的点进行特殊的处理。
1
本题先使用树的直径（可用树形 DP，分别处理每个点向下的非严格次长/最长深度）处理掉没有越过环的情况。然后对于环上的点，可以处理到达的最深深度，然后用前缀和处理距离，用单调队列查询在下标范围内的答案。
2
母题的变式，变成了基环树。考虑断掉环上的一边，然后进行特殊处理再树形 DP。
3
类似于2，但是树形 DP 的转移可以参考子树信息—变式（贪心）的做法。
规律
发现状态的表示无非是单个点为根的答案或子树的答案，然后记录一些特殊的属性（选择情况、选择个数）。
树形 DP 可能作为算法的一部分。
基环树的分成处理环上或断环。
还有部分小技巧（贪心）