OI - 树上染色(洛谷) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 树上染色(洛谷)

发表于 分类于 Valine：

洛谷上好多 O2 过了的假算法啊 → →

# 题面

> Linked 洛谷 P3117

点击展开/折叠题面

有一棵点数为 $n$ 的树，树边有边权。给你一个在 $0 \sim n$ 之内的正整数 $k$，你要在这棵树中选择 $k$ 个点，将其染成黑色，并将其他的 $n-k$ 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。

# 解析

先从暴力开始想，即 $f_{u,i}$ 表示 $u$ 的子树中，有 $i$ 个白点，此时已经确定的受益最大值。

（我一开始还想错了 QwQ）若 $u$ 的子树内有 $i$ 个白点，那 $u$ 的子树外有 $k-i$ 个白点，于是 $u$ 到 $u$ 的父亲的边对于白点来说提供了 $(k-i)i$ 次贡献，对于黑点同理。则 $u$ 到父亲的边 $e$ 总贡献为 $C(u,i)=val_e[(k-i)i+(siz_u-i)(n-k-siz_u+i)]$。

这就是一个背包问题，于是就有下面的递推式：

树形背包过程中涉及到两个背包（即“$u$ 与 $v$ 之前子节点的背包”和“子节点 $v$ 的背包”）的合并，如果直接合并，因为第二维是 $O(n)$ 的，理论复杂度合并一次是 $O(n^2)$，总复杂度 $O(n^3)$。但是跑不满，可以利用 $v$ 子树的背包第二维最大只有 $siz_v$ 优化一下，卡一卡还是能过。

我想到的是一种 $O(n^2\log n)$ 的算法，利用了树上启发式合并的思想。

考虑合并背包的过程：最初 $u$ 的背包只是 $u$ 单点，大小为 $1$；然后和 $u$ 的子节点依次合并。

所以我就想，$u$ 先和它的重儿子合并，然后再和它的轻儿子合并，就可以做到 $O(n^2\log n)$。

为什么？分开考虑。

考虑 $u$ 和它的重儿子 $v$ 合并，因为是第一次合并，$u$ 的背包大小为 $1$，$v$ 的背包大小为 $siz_v$，粗略看为 $O(n)$，这样两个背包合并是 $O(n)$ 的。于是对于每个 $u$ 都会有这样一次合并，于是复杂度是 $O(n^2)$。

考虑 $u$ 和它的轻儿子 $v$ 合并，此时 $u$ 已经和一些子节点合并过了，背包大小为 $O(n)$；$v$ 的背包大小为 $siz_v$。由树上启发式合并可得，记 $lson_u$ 是 $u$ 的轻儿子点集：

而合并 $v$ 与 $u$ 的背包的复杂度粗略记作 $O(n\times siz_v)$（因为其实 $u$ 的背包大小比 $n$ 小），则有：

因此总复杂度为 $O(n^2\log n)$。

# 源代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=2010;
#define cmax(a,b) a=max(a,b);

int n,m;
int siz[N],wei[N],edg[N];
ll f[N][N],tmp[N];

struct GRAPH{
	int head[N],nxt[N<<1],to[N<<1],val[N<<1],ncnt;
	void AddEdge(int u,int v,int cst){
		int p=++ncnt,q=++ncnt;
		nxt[p]=head[u],to[p]=v,val[p]=cst,head[u]=p;
		nxt[q]=head[v],to[q]=u,val[q]=cst,head[v]=q;
	}
	int operator [](const int &u){return head[u];}
}Gr;

inline int Ri(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r;
}
void DFS(int u,int fa){
	siz[u]=1;
	for(int it=Gr[u];it;it=Gr.nxt[it]){
		int v=Gr.to[it];
		if(v==fa) continue;
		DFS(v,u);
		siz[u]+=siz[v];
		if(siz[wei[u]]<siz[v]) wei[u]=v,edg[u]=Gr.val[it];
	}
}
void Solve(int u,int fa,int las){
	if(wei[u]){
		int v=wei[u];
		Solve(v,u,edg[u]);
		for(int i=0;i<=siz[v];i++){
			//u is white
			cmax(f[u][i+1],f[v][i]);
			//u is black
			cmax(f[u][i],f[v][i]);
		}
	}
	int now=1+siz[wei[u]];
	for(int it=Gr[u];it;it=Gr.nxt[it]){
		int v=Gr.to[it];
		if(v==fa || v==wei[u]) continue;
		Solve(v,u,Gr.val[it]);
		int li=min(siz[v],m),lj=min(now,m);
		for(int i=0;i<=li;i++)
			for(int j=0;j<=lj;j++)
				cmax(tmp[i+j],f[v][i]+f[u][j]);
		now+=siz[v];
		for(int i=min(now,m);i>=0;i--) f[u][i]=tmp[i],tmp[i]=0;
	}
	for(int i=min(now,m);i>=0;i--)
		f[u][i]+=((ll)i*(m-i)+(ll)(siz[u]-i)*(n-m-siz[u]+i))*las;
}
int main(){
	n=Ri(),m=Ri();
	for(int i=1;i<n;i++){
		int u=Ri(),v=Ri(),cs=Ri();
		Gr.AddEdge(u,v,cs);
	}
	DFS(1,0);
	Solve(1,0,0);
	printf("%lld\n",f[1][m]);
	return 0;
}

THE END

Thanks for reading!

> Linked 那一天从梦中醒来-网易云