树上背包的复杂度证明

尚未归档

今天我发现树上背包的复杂度并非如我想象一样是 \(O(n^2)\) 的，而是 \(O(nm)\) 的。我们来看看证明吧。

定义：什么是树上背包？

此处的树上背包定义如下：

void dfs(int u,int fa)
{
    sz[u]=1;
    for(int k=head[u];k;k=e[k].next)
    {
        int v=e[k].to;
        if(v==fa) continue;
        dfs(v,u);
        for(int j=0;j<=min(m,sz[u]);++j)
            for(int k=0;k<=min(m-j,sz[v]);++k)
                // dp[u][j+k] <- dp[u][j] * dp[v][k]
    }
}

¹

树上背包可以理解为是把所有子树的信息合并了起来。接下来我们要证明它的复杂度是 \(O(nm)\)。

多叉树转二叉树

这一步其实没有什么必要，但是这样简单一点。

我们做书上背包的时候，不是把一个前缀所有的子树与下一个子树合并吗？把这个合并当成一个二叉（前缀的子树是左叉，下一个子树是右差）就可以了。

分类讨论

首先明确一点：一个子树的大小要么 \(<m\) 要么 \(=m\)，因为它 \(>m\) 的部分会被截断不参与后面的计算。

• 如果两个子树中至少有一个 \(大小=m\)：设另一个的 \(大小=k\)，那么本次合并的复杂度是 \(O(mk)\)，且合并之后父节点只剩 \(m\) 的大小，可以理解为消去了 \(k\) 的大小。这样最多消去 \(\dfrac{n}{k}\) 次，因此复杂度是 \(O(mk\dfrac{n}{k})=O(nm)\) 的。

• 如果两个子树的大小都 \(<m\)：

  • 如果合并完的子树大小 \(<m\)：这种的合并相当于是把两边子树中的点在 LCA 处产生 \(O(1)\) 的复杂度。对于这整棵子树，产生的总共复杂度为其中点两两匹配产生的复杂度，为 \(O(size^2)\)。不过我们暂时不管。我们会在它的祖先计算它的复杂度。
  • 如果合并完的子树大小 \(=m\)：根据上一条，对于这样一个分叉，两侧的子树内会产生 \(O(size^2)<O(m^2)\) 的复杂度，而本次的合并会产生 \(O(size_{ls}size_{rs})\) 的复杂度，总的来说没有超过 \(O(m^2)\) 的量级。我们称呼一个这样的合并所在的子树为一个“S结构”，那么显然这种结构没有互相包含关系。因此，这样的合并在全局最多发生 \(\dfrac{n}{m}\) 次，每次复杂度为 \(O(m^2)\)，总的复杂度就在 \(O(nm)\) 量级。
  • 第一种情况还有一种情况没被考虑： 如图。标粗的点的大小 \(=m\)，而其他点大小 \(<m\).
  • 我们发现这种情况就是最开始说的那种情况（两个子树中至少有一个 \(大小=m\)）。而这颗 \(<m\) 的子树内部产生的复杂度是小于 \(O(m^2)\) 的，对这种情况只是一个常数级复杂度。

综上所述，我们证明了树上背包的复杂度是 \(O(nm)\) 的。别看我们证明中忽略了常数，其实常数是很小的。

实测

以 P3177 [HAOI2015] 树上染色 为例，HTC 的代码在 \(n=10^5,k=10^3\) 的数据下只转移了 \(10^8\) 次，说明随机数据下常数几乎为 \(1\).（当然也可能是我们数据太水了）

---

1. 转载并修改自 https://www.cnblogs.com/AWhiteWall/p/14030045.html ↩