树上背包的上下界优化

最近做了几道树上背包的题目,很多题目的数据范围都很小,但实际上树上背包有多种方式可以优化到 $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$ 个节点。

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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]);
}
}
}
}

上下界优化

注意背包转移的这部分:

1
2
3
4
5
6
7
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$ 的枚举范围进行优化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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$)

大约需要这样写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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)$ 做法

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

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

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