再谈树上背包的上下界优化

关于树上背包的上下界优化，当时 fz 推荐我读的是 ouuan 的文章（cnblogs github pages），但是，我现在认为那里面的复杂度证明存在问题。

一般情况

树上背包的上下界优化指的是类似如下的结构：

void dfs(int u, int fa){
    dp[u] = {0}; // initialization
    for(int v: g[u]){
        if(v == fa) continue;
        dfs(v, u);
        // merge dp[u] and dp[v]
        vector<int> tmp(dp[u].size() + dp[v].size());
        for(int i = 0; i < dp[u].size(); i++){
            for(int j = 0; j < dp[v].size(); j++){
                tmp[i + j] = max(tmp[i + j], dp[u][i] + dp[v][j]);
            }
        }
        dp[u] = tmp;
    }
}

我们可以证明，上面的 dp 复杂度为 $O(n^2)$。

形象的证明方式¹

dp 数组的大小与子树大小相关，所以我们考虑将 dp 值与子树内的结点一一对应，由此不难发现，每一个点对会且只会在 lca 处合并一次，故总复杂度为 $O(n^2)$。

严格的证明方式¹

令 $T(u)$ 表示处理 $u$ 子树所需的时间，我们考虑用归纳法证明 $T(u)\le siz_u^2$。

注意这里不能将渐进记号带进去算，否则我们可以用类似的方式证明如果有 $T(n)=T(n-1)+n$，则 $T(n)=O(n)$，这显然是不正确的。

对于叶子结点我们有 $T(leaf)=1=siz_{leaf}^2$。

对于非叶子结点，我们有
$$
\begin{aligned}
T(u)&=\sum_{v\in son_u} T(v)+\sum_{v,w\in son_u,v<w} siz_v siz_w\\
&=\sum_{v\in son_u} siz_v^2+\sum_{v,w\in son_u,v<w} siz_v siz_w\\
&<\left(\sum_{v \in son_u}siz_v\right)^2\\
&<siz_u^2
\end{aligned}
$$
于是我们就证明了总复杂度为 $O(n^2)$。

推广情况

若我们的 dp 数组长度有上限 $m$，我们可以证明总复杂度为 $O(nm)$。

void dfs(int u, int fa){
    dp[u] = {0}; // initialization
    for(int v: g[u]){
        if(v == fa) continue;
        dfs(v, u);
        // merge dp[u] and dp[v]
        // here the size of tmp is limited by m
        vector<int> tmp(min(m, dp[u].size() + dp[v].size()));
        for(int i = 0; i < dp[u].size(); i++){
            for(int j = 0; j < dp[v].size() && i + j < m; j++){
                tmp[i + j] = max(tmp[i + j], dp[u][i] + dp[v][j]);
            }
        }
        dp[u] = tmp;
    }
}

形象的证明方式²³

考虑将 dp[u] 的元素与已合并部分中先序遍历时间戳最后的 $m$ 个结点一一对应，待合并的 dp[v] 则将其中元素与子树内时间戳最前的 $m$ 个结点对应，容易发现这样操作后，所有被合并的点对均满足先序遍历时间戳之差不超过 $2m$，同时每个点对仍然至多只能在 lca 处合并一次，故总复杂度为 $O(nm)$。

严格的证明方式⁴

我们的操作是依次合并 dp 数组，故考虑将原树转化为二叉树（儿子多的依次合并，儿子少的补上），注意转化过后树的结点数依然为 $O(n)$。

• 根据一般情况，我们知道对于 $siz_u\le m$ 的结点，处理这一子树所需时间不超过 $siz_u^2$。
• 对于 $siz_u>m$，$siz_{lson},siz_{rson}\le m$ 的结点，这些结点之间必然没有祖先关系，所以我们有 $\sum siz_u\le n$，处理这些子树所需的总时间为 $\sum siz_u^2$，考虑 $siz_u$ 有上界 $2m+1$，故总时间是 $O(nm)$ 级别的。
• 对于有且仅有一个儿子大小 $\le m$ 的结点，较小的儿子之间必然没有祖先关系，所以合并所需的时间是 $O(nm)$ 级别的。
• 对于两个儿子大小都 $>m$ 的结点，这样的结点个数是 $O(n/m)$ 级别的，单次合并所需时间为 $m^2$，故合并所需时间是 $O(nm)$ 级别的。

于是总复杂度是 $O(nm)$ 级别的。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。