树形 dp
普通树形 dpψ(｀∇´)ψ
通常来说树形 dp 都是需要你处理一些，连通块啊，子树相关的问题。
状态一般设计为 \(dp(u, ...)\) 表示，考虑以 \(u\) 为子树，在一些限制条件下能得到的信息。
转移直接考虑枚举子树进行转移即可，通常需要预先/同步处理子树大小，节点深度，路径长度一类的信息方便转移。
一个简单的例子：
某大学有 \(n\) 个职员，编号为 \(1\ldots n\)。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 \(r_i\)，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
\(1\le n \le 6\times 10^3\)（这题出处是 URAL，远古机子所以数据范围不大）
显然可以设 \(dp(u, 0/1)\) 表示，考虑以 \(u\) 为根的子树，\(u\) 去或者不去，能得到的最大价值。
转移很显然：
这告诉我们，树形 dp 通常转移都是考虑，儿子和父亲之间的关系来转移的。
子树的合并ψ(｀∇´)ψ
默认读者已经阅读过 背包 dp 中的树形背包部分。
一个值得注意的事情是，类似树形背包这种，需要把子树的状态合并上来的 dp 问题，我们都免不了枚举分给子树的空间，并枚举整体的空间，这样复杂度是立方级别的（假设所有变量同阶）。
那么，有没有什么办法来优化这个过程呢？其实，说不上算有。
有一个小 trick 是，如果状态数量和子树大小相同（比如树形背包体积为 \(1\)，连通块大小），那么我们每次合并两个子树，这样做的复杂度是 \(O(n^2)\) 的。
不过还有一个技巧，可以做进一步的优化。
先看一个例子：
给一颗 \(n\) 个点的有根树，点有点权，求包含根且点权总和不超过 \(m\) 的连通块数量。
\(1\le n\le 1000, m\le 10^5\)。
不妨设 \(dp(u, i)\) 表示，\(u\) 的子树中，包含 \(u\) 的，点权总和不超过 \(i\) 的连通块数量。
每次考虑枚举子树的状态，合并上来，因为有 \(i\) 的限制，并且这里，对于 \(dp(u)\) 来说，它的状态数量和子树大小是不相等的，所以如果暴力合并，总复杂度是 \(O(nm^2)\) 的。
但是我们有一个神奇优化，我们考虑 dfs 序！
就是，这个包含 \(u\)，实际上和树形背包那个选 \(u\) 限制是类似的，如果这个点不选，子树里的都不用考虑了。
那么用 dfs 序变成序列，考虑一下每个点是否选择，如果不选择，就要跳过这个子树。
那么问题就变成了序列上的问题，设 \(dp(i)\) 表示在有限制的前提下，选不超过 \(i\) 的方案数，复杂度就是 \(O(nm)\) 了。
这题找不到提交的地方，找到了再说把。
但是树形背包如果体积为 \(1\) 也可以用类似的方法优化，所以先用选课那个题代替吧（）
子树外的影响ψ(｀∇´)ψ
这个技巧来源于某次模拟赛，因为保密原因不在这里放出。
如果是 cwoi 的同学应该知道密码是什么，link（这里面的 T4）
这个题解还没完成，还要补（TODO）
换根 dpψ(｀∇´)ψ
一般来说换根 dp 都是要对于每个节点都求一个信息。
不妨先考虑对于一个节点 \(rt\) 怎么做，求出一个答案，然后考虑从上往下转移。
这时，就只需要利用一些提前计算好的信息，从父亲转移到儿子就行了（这里的父子关系沿用 \(rt\) 为根时的定义）。
实际上就是，把以 \(fa\) 为根的答案，通过一些计算，转移成以 \(u\) 为根的答案。
举个简单的例子：
[POI2008]STA-Station：
给你一颗无根无权树，请你找到一个节点，使得以这个节点为根的时候，树的节点的深度之和最大。
要求 \(O(n)\) 计算。
首先以 \(1\) 为根，记 \(dp(u)\) 表示考虑 \(u\) 的子树的深度之和。
考虑求出 \(dp\)，然后 \(dp(1)\) 就是 \(ans(1)\)，我们考虑转移。
假设 \(fa\) 的答案 \(ans(fa)\) 已经求出，考虑 \(ans(u)\) 怎么转移。
现在以 \(u\) 为根，那么原来是 \(u\) 的子树的还是子树，这个从 \(dp(u)\) 就能得到，唯一的变化是 \(fa\) 和以 \(fa\) 为根时除了 \(u\) 的所有子树构成的连通块现在变成了 \(u\) 的新的子树，我们只需要处理这部分的贡献就行了。
类似这张图：
可以发现绿色部分就是多出来的，这部分里的每一个节点相比原来，走到新的根 \(u\) 都要多走 \(1\) 的距离，深度和整体会加上 \(n - siz(u)\)。
然后它们本来到 \(fa\) 的距离就是 \(ans(fa) - dp(u) - siz(u)\)。
所以 \(ans(u) = ans(fa) - dp(u) + n - 2siz(u)\)，实现的时候可以合并 \(ans, dp\) 两个数组。
有些时候，问题不是 \(\sum\) 而是 \(\min \max\)，这时候就需要再处理次最值来正确转移，因为有可能 \(u\) 就是 \(fa\) 取到最值的转移点，我们要扣除 \(u\) 的影响再转移，这点请读者留意。