https://www.luogu.com.cn/problem/P3177
今天做这题的时候发现自己的树上背包是假的，特来记录一下。
其实很简单，因为把某个子树 \(v\) 合并进其父亲 \(u\) 时转移的次数是 \(siz_v\) 乘上当前 \(siz_u\)，也就是在 \(u\) 在 \(v\) 前面的子树大小之和。所以任意两个结点只会在它们的 LCA 处进行一次转移，时间复杂度就是 \(O(n^2)\)。
但在具体写的时候容易先把 \(siz_u\) 加进 \(siz_v\)，这样总次数就加上了所有子树大小的平方，变成了 \(O(n^3)\)。
所以这么写就得加个下界，若转移后体积为 \(j\)，转移体积为 \(p\)，则 \(j-p>siz_u-siz_v\) 的转移是无意义的，因为原先的体积不可能大于 \(siz_u-siz_v\)，所以 \(p\) 的下界是 \(\max(0,j+siz_v-siz_u)\)。
注意到背包体积为 \(k\)，所以实际复杂度应为 \(O(nk)\)。分析起来也很简单，当 \(siz_u\leq k\) 的时候自然没有影响，因为最坏情况都是大小为 \(k\) 的子树为 \(O(k^2\times\frac{n}{k})=O(nk)\)；当 \(siz_u>k\) 时，每多一个 \(k\times\min(siz_v,k)\)，就会把 \(siz_v\) 合并进 \(siz_u\)，这样一个大小为 \(siz_v\) 的子树就消失了，所以在 \(siz_v\leq k\) 时的合并也是 \(O(nk)\)；\(siz_v>k\) 时最多合并 \(\frac{n}{k}\) 次，乘上 \(k^2\) 还是 \(O(nk)\)。