「HAOI 2015」树上染色

Description

题目链接:BZOJ 4033

有一棵 $N$ 个节点的树(有边权),选择 $K$ 个点染成黑色,其他点染成白色。最后得到的收益为“黑点两两之间的距离和,白点两两之间的距离和”之和,要求最大化收益。

数据范围:$0\le K\le N\le 2000$


Solution

显然这是一道树形 $\text{DP}$ 题目,我们设 $f[i][j]$ 表示以 $i$ 为根节点的树中染了 $j$ 个黑点获得的最大收益。

在处理完子树 $v$ 中,我们加入边 $E(u,v)$($u$ 是 $v$ 的父亲),则 $E(u,v)$ 的贡献为

每次树形 $\text{DP}$ 时,先把子树 $v$ 和以 $u$ 为根的树中已经计算完的部分进行 $01$ 背包合并,最后计算 $u$ 对其父亲的贡献即可(以便接下来的递归计算)。

时间复杂度:$O(N^2)$


Code

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=2005;
int n,m,tot,hd[N],sz[N];
long long f[N][N],val[N];
struct Edge{
int to,nxt,w;
}e[N<<1];

void add(int u,int v,int w) {
e[++tot].to=v;
e[tot].w=w;
e[tot].nxt=hd[u];
hd[u]=tot;
}
void dfs(int u,int fa) {
f[u][0]=f[u][1]=0; sz[u]=1;
for(int i=hd[u];i;i=e[i].nxt) {
int v=e[i].to;
if(v==fa) continue;
val[v]=e[i].w;
dfs(v,u);
for(int k=min(sz[u],m);k>=0;--k)
for(int j=min(sz[v],m-k);j>=0;--j)
f[u][k+j]=max(f[u][k+j],f[u][k]+f[v][j]);
sz[u]+=sz[v];
}
for(int i=0;i<=min(sz[u],m);++i)
f[u][i]+=val[u]*(i*(m-i)+(sz[u]-i)*(n-m-(sz[u]-i)));
}
int main() {
scanf("%d%d",&n,&m);
for(int u,v,w,i=1;i<n;++i) {
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w);
}
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) f[i][j]=-(1LL<<60);
dfs(1,0);
printf("%lld\n",f[1][m]);
return 0;
}

Complexity

看起来树形 $\text{DP}$ + 背包的复杂度为 $O(N^3)$,但是实际上我们发现枚举的范围是 $0\le k\le sz[v]$,$0\le j-k\le sz[u]-sz[v]$,那么总的枚举次数为 $\sum(sz[u]-sz[v])\times sz[v]$。

而 $\sum sz[v]=sz[u]$,那么复杂度为 $sz[u]^2-\sum sz[v]^2$。以此向上推,则到根节点时复杂度为 $O(N^2)$。

0%