BZOJ4033 [HAOI2015]树上染色

Vexoben

Jun 18, 2018

It takes 3 minutes to read this article.

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4033

（刷新以获取数学公式）

题意

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

$N,K<=2000$

题解

对于一条边，假设去掉它后分成的两个联通块中，黑色节点个数分别为 $b_1,b_2$ ，白色节点个数分别为 $w_1,w_2$ ，则定义它的贡献 $con=weight*(b_1*b_2+w_1*w_2)$

定义状态 $f[i][j]$ 表示以 $i$ 为根的子树，有 $j$ 个点被染成黑色，子树内的边产生的最大贡献和。

转移的时候，将节点 $x$ 的子树一个个加入。设 $y$ 是当前转移到的儿子，转移方程是：

$f[x][i]=max(f[x][i],max(f[x][j]+f[y][i-j]+con(x,y)))$

其中 $con(x,y)$ 是边 $(x,y)$ 产生的贡献，它的值为:

$weight(x,y)*((i-j)*(K-i+j)+(size[y]-i+j)*(n-m-size[y]+i-j))$

这样复杂度看起来是 $O(n^3)$ 的。但是我们分析一下会发现复杂度为:

对于点对 $(u,v)$ ，仅在 $x=LCA(u,v)$ 的时候对答案有贡献，从而复杂度是 $O(n^2)$ 的。

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int N=2050;

int n,m,E;
int fa[N],siz[N],fir[N],nex[N<<1],arr[N<<1];
LL g[N],len[N<<1],f[N][N];

inline void Add_Edge(int x,int y,LL l) {
	nex[++E]=fir[x];
	fir[x]=E; arr[E]=y; len[E]=l;
}

void dfs(int x) {
	siz[x]=1;
	for (int i=fir[x];i;i=nex[i]) {
		if (arr[i]==fa[x]) continue;
		fa[arr[i]]=x; dfs(arr[i]);
		int sx=min(m,siz[x]);
		int sy=min(m,siz[arr[i]]);
		memset(g,0,sizeof(LL)*(m+1));
		for (LL j=0;j<=sx;j++)
			for (LL k=0;k<=sy;k++) {
				if (j+k>m) break;
				LL eval=len[i]*(k*(m-k)+(siz[arr[i]]-k)*(n-m-siz[arr[i]]+k));
				g[j+k]=max(g[j+k],f[x][j]+f[arr[i]][k]+eval);
			}
		for (int j=0;j<=m;j++) f[x][j]=g[j];
		siz[x]+=siz[arr[i]];
	}
}

int main() {
	scanf("%d%d",&n,&m);
	for (int i=1;i<n;i++) {
		int x,y; LL l; scanf("%d%d%lld",&x,&y,&l);
		Add_Edge(x,y,l); Add_Edge(y,x,l);
	}
	dfs(1);
	printf("%lld",f[1][m]);
	return 0;
}