哦咦咦啊咦哦咦咦咦啊咦哦咦咦啊咦哦咦咦咦啊咦哦咦咦啊咦哦咦咦咦啊咦哦咦咦啊咦哦咦咦咦啊咦哦咦咦啊咦哦咦咦咦啊咦哦咦咦啊咦哦咦咦咦啊咦
\(O(n^2)\) 树上背包
\(O(n^2)\) 伪（人）代码:
for v in graph[u]:for i from 1 to size[u]:for j from 1 to size[v]:dp转移size[u]+=size[v]
复杂度证明
这实际上是在枚举点对，\(i\) 代表从 \(u\) 之前已经合并的子树中选出的节点数量。
\(j\) 代表从当前子节点 \(v\) 的子树中选出的节点数量。
对于整棵树中的任意两个节点 \(x\)，\(y\)，它们一定有一个最近公共祖先（LCA），设为 \(L\)。
在遍历的过程中，只有当 DFS 回溯到 \(L\) 时，\(x\) 和 \(y\) 会进入到同一个状态转移方程里计算。
在 \(L\) 处，必然有一个时刻，正在把包含 \(x\) 的子分支合并到包含 \(y\) 的主分支（或者反过来）。
这时，内层循环枚举到了 \(x\) 所在的那部分大小，外层循环枚举到了 \(y\) 所在的那部分大小，于是 \(x\) 和 \(y\) 产生了一次贡献。
所以，对于任意两个节点，只会在它的 LCA 处被计算一次。
复杂度:\(O(\frac{n\cdot(n-1)}{2})\approx O(n^2)\)
\(O(nm)\) 树上背包
伪代码：
for v in graph[u]:for i from 1 to min(size[u],m):for j from 1 to min(size[v],m):dp转移size[u]+=size[v]
复杂度证明
写不下了，记得看课件！
换根dp初步
例题：HDU 2196 Computer