关于树形背包复杂度的证明

· · 个人记录

我们考虑树形背包的子树合并方法，既对于每一个点 x，遍历它的所有儿子 y，每次转移形如 f[x][a+b] = \sum combine(f[x][a],f[y][b])。其中 combine 操作的复杂度是 \Theta(1) 的，f 为背包数组。

因此，我们可以把优化过上下界的for循环写成如下的伪代码：

for(y 是 x 的 儿子)
    for(a = 1; a <= K && a <= s[x]; a++)
        for(b = 1; b <= s[y] && b + a <= K; b++)
            f[x][a + b] = combine(f[x][a], f[y][b]);

其中 s 为子树大小数组。为方便起见，我们把后两层循环称作一次更新。

用慧眼法不难得出上式的复杂度为 \Theta(\min(s[x],K) \times \min(s[y],K))，所以我们可以知道该算法的复杂度为 O(nK^2)，其中 n 是树的大小，K 是背包大小。

同时，我们发现循环到 x 的儿子 z 时，设已经处理过的 x 的子树中的点组成的集合为 A（不包含 x）, z 的子孙及自己组成的点集为 B，则这次更新的复杂度为 \Theta(|A||B|)。因此，我们可以把复杂度 \Theta(1) 地均摊到每一个点对 (u,v) 上，其中 u \in A，v \in B 。而此时 x 就是 u 和 v 的最近公共祖先，换句话说，就是对于点对 (u,v)，当且仅当我们处理的 x 是它们的最近公共祖先时，它们才会贡献 \Theta(1) 的复杂度。所以整体复杂度 O(n^2)。我们把此结论记为结论1，后面会用到。

以上是铺垫，现在开始证明复杂度为 O(nK) 。

我们设大小小于等于 K 的子树为小子树，大小大于 K 的子树为大子树。我们称一个以 x 为根的 小子树 是 极大的 当且仅当以 x 的父亲为根的子树是一颗 大子树。同理，我们称一颗以 x 为根的 大子树 是 极小的 当且仅当所有以 x 的儿子为根的子树都是 小子树 。

我们能够注意到，若一颗 极小的大子树 的根为 x，则以 x 的儿子为根的子树都是 极大的小子树，且一颗 极大的小子树 的根若为 y，则以 y 的父亲为根的子树是一颗 极小的大子树。

所以所有的 极大小子树 x_1,x_2,\dots,x_m 合并起来组成了所有的 极小大子树。它们合并起来的过程是 O(K\sum_{i=1}^m |x_i|) 的。因为 极大小子树 是互不包含的，所以 \sum_{i=1}^m |x_i| \leq n。因此消除所有 极大小子树 的复杂度是 O(nK) 的。

这些 极大小子树 内部各自合并的复杂度为 O(\sum_{i=1}^m |x_i|^2)（由结论1）。我们不妨设 x_1 \geq x_2 \geq \dots \geq x_n，则将 x_i 增加 1 ，同时将 x_{i+1} 减小 1 会使 \sum_{i=1}^m |x_i|^2 变大，所以 \sum_{i=1}^m |x_i|^2 \leq K^2 \times \dfrac{n}{K}=nK。因此合并出所有的 极大小子树 的复杂度是 O(nK)。

最后，考虑到所有的 极小大子树 最多有 \dfrac{n}{K} 个，且互不重叠，所以将它们合并起来复杂度为 O(K^2 \times \dfrac{n}{K}) = O(nK)。

上述三个步骤的复杂度组合起来便是整个代码的复杂度，即 O(nK)。

证毕