树上背包的上下界优化

文章目录

【注意】最后更新于 February 14, 2020,文中内容可能已过时,请谨慎使用。

最近做了几道树上背包的题目,很多题目的数据范围都很小,但实际上树上背包有多种方式可以优化到 $O(nm)$ ($n$ 为节点数,$m$ 为体积的值域),比如先序遍历优化(何森《先序遍历用于优化树形背包问题》),求泛化物品的并(徐持衡《浅谈几类背包题》)……经过一番学习,觉得还是上下界优化理解起来最简单,也比较好写,适用范围广,唯一比其它做法复杂的地方就是复杂度分析。

例题讲解

这里以一道经典的树上背包作为例题:【数据加强版】选课

直接把我出的数据加强版放上来了..反正题面里有原题链接QAQ

注:本文中用 $a_i$ 代指题面中的 $s_i$ 。

$O(nm^2)$ 做法

用 $f_{u,i}$ 表示以 $u$ 为根的子树中选 $i$ 门课的最大得分,那么 $f_{u,i}=\min\limits_{\forall fa[v_j]=u,\sum k_j=i-1}(\sum f[v_j][k_j])+a_u$,而这个转移可以通过背包实现,依次合并每棵子树,每次合并时枚举 $i$ 和 $k_j$ ,$f_{u,i}=\max(f_{u,i},f_{u,i-k_j}+f_{v_j,k_j})$ 。

需要倒序枚举 $i$ 防止状态在转移前被覆盖。否则的话dp数组要多一维。

由于可能是森林,所有没有直接先修课的节点,父亲视为节点 $0$,实际上就要选 $m+1$ 个节点。

参考代码:

void dfs(int u)
{
    f[u][1]=a[u];
    int i,j,k,v;
    for (i=head[u];i;i=nxt[i])
    {
        v=to[i];
        dfs(v);
        for (j=m+1;j>=1;--j)
        {
            for (k=1;k<j;++k)
            {
                f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
            }
        }
    }
}

上下界优化

注意背包转移的这部分:

        for (j=m+1;j>=1;--j)
        {
            for (k=1;k<j;++k)
            {
                f[u][j]=max(f[u][j],f[u][k]+f[v][j-k]);
            }
        }

实际上,这里面有很多状态都是没有意义的:

  1. 转移时已经合并了大小之和为 $s$ 的一些子树,那么 $f_{u,i}(i>s)$ 实际上是没有意义的。

  2. $f_{v,i}(i>siz[v])$ 也是没有意义的。

  3. $f_{u,i}(i>m)$ 是没有作用的。

所以,可以对 $j$ 和 $k$ 的枚举范围进行优化:

void dfs(int u)
{
    siz[u]=1;
    f[u][1]=a[u];
    int i,j,k,v;
    for (i=head[u];i;i=nxt[i])
    {
        v=to[i];
        dfs(v);
        for (j=min(m+1,siz[u]+siz[v]);j>=1;--j)
        {
            for (k=max(1,j-siz[u]);k<=siz[v]&&k<j;++k)
            {
                f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
            }
        }
        siz[u]+=siz[v];
    }
}

复杂度分析

可以参考这篇博客

形象的解释

每个点对都只会在 $lca$ 处合并一次,所以总的复杂度是 $O(n^2)$ 的。

这个解释很简洁,需要自己意会一下..

粗略计算

令 $T_u$ 为处理子树 $u$ 的总用时,那么:

$$\begin{aligned}T_u&=\left(\sum\limits_{\forall fa[v_i]=u}T_{v_i}\right)+t_u\\t_u&=1+(1+siz[v_1])\times siz[v_1]+(1+siz[v_1]+siz[v_2])\times siz[v_2]+\cdots+siz[u]\times siz[v_k]\\&=1+\sum\limits_{\forall fa[v_i]=u}siz[v_i]\times(siz[u]+1)\\&=siz[u]^2\end{aligned}$$

对于叶子节点 $u$ ,$T(u)=1$ ,是 $O(siz[u]^2)$ 的。

对于儿子都是叶子节点的节点 $u$,由于平方和小于和平方,$\sum\limits_{\forall fa[v_i]=u}T_{v_i}$ 也是 $O(siz[u]^2)$ 的。

可以这样递归地说明,对于任意节点 $u$ ,$\sum\limits_{\forall fa[v_i]=u}T_{v_i}$ 都是 $O(siz[u]^2)$ 的。

又因为 $t(u)$ 是 $O(siz[u]^2)$ 的,$T(u)$ 就是 $O(siz[u]^2)$ 的。

所以解决整个问题就是 $O(n^2)$ 的。

考虑值域的计算

枚举过程中还要对 $m$ 取 min ,所以应该是这样的:

$$\begin{aligned}t_u&=1+\min(m,1+siz[v_1])\times \min(m,siz[v_1])+\min(m,1+siz[v_1]+siz[v_2])\times \min(m,siz[v_2])+\cdots+\min(m,siz[u])\times \min(m,siz[v_k])\\&\le m\times siz[u]\end{aligned}$$

所以,$t(u)$ 是 $O(\min(siz[u],m)\times siz[u])$ 的。

对于 $siz[u]\le m$,$T(u)$ 是 $O(siz[u]^2)$ 的。

对于 $siz[u]>m$,$\sum\limits_{\forall fa[v_i]=u,siz[v_i]\le m}T_{v_i}$ 是 $O\left(\left(\sum\limits_{\forall fa[v_i]=u,siz[v_i]\le m}siz[v_i]\right)^2\right)$ 的;$\sum\limits_{\forall fa[v_i]=u,siz[v_i]>m}T_{v_i}$ 是 $O\left(m\times\sum\limits_{\forall fa[v_i]=u,siz[v_i]>m}siz[v_i]\right)$ 的;所以,$T(u)$ 是 $O(m\times siz[u])$ 的。

所以,解决整个问题是 $O(nm)$ 的。

其它例题

【数据加强版】道路重建

dl代码

我出的那两道数据加强版略有些毒瘤..($n\times m\le 10^8$)

大约需要这样写:

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

void dfs(int u);
void add(int u,int v);

const int N=100010;

int head[N],nxt[N],to[N],cnt;
int n,m,a[N],f[100000010],siz[N];

int main()
{
    int i,k;

    scanf("%d%d",&n,&m);

    for (i=1;i<=n;++i)
    {
        scanf("%d%d",&k,a+i);
        add(k,i);
    }

    dfs(0);

    printf("%d",f[m+1]);

    return 0;
}

void add(int u,int v)
{
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
}

void dfs(int u)
{
    siz[u]=1;
    f[u*(m+2)+1]=a[u];
    int i,j,k,v;
    for (i=head[u];i;i=nxt[i])
    {
        v=to[i];
        dfs(v);
        for (j=min(m+1,siz[u]+siz[v]);j>=1;--j)
        {
            for (k=max(1,j-siz[u]);k<=siz[v]&&k<j;++k)
            {
                f[u*(m+2)+j]=max(f[u*(m+2)+j],f[u*(m+2)+j-k]+f[v*(m+2)+k]);
            }
        }
        siz[u]+=siz[v];
    }
}

关于另一种 $O(nm)$ 做法

一开始我在洛谷发了篇选课的题解,然后没过…

那篇题解 用的是求泛化物品的并(徐持衡《浅谈几类背包题》)

虽然说洛谷好像还没有上下界优化的题解..但最近好几篇题解没过审,都不太想在洛谷发题解了…

评论正在加载中...如果评论较长时间无法加载,你可以 搜索对应的 issue 或者 新建一个 issue