BZOJ 4033 [HAOI2015]树上染色

题目大意

给你一棵树，边有边权。给你一个$0 \sim n$之间的正整数$k$，染$k$个点为黑色，另外$n-k$个点为白色，使得黑点两两之间的距离加上白点两两之间距离的和最大。

树形背包DP.

设$f_{i,j}$表示i的子树有$j$个黑点的该子树对答案贡献的最大值。之后加入一个点后向外的贡献进行统计，直接统计到子树外的边权和即可。

合并要讲究基本法啊大兄dei

从pos和to[i]的siz向下枚举并加和，最后用to[i]的siz更新pos的siz。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,siz[2010];
long long f[2010][2010];
int to[4010],nxt[4010],val[4010],head[2010],tot;
inline void ae(int x,int y,int z){to[++tot]=y,nxt[tot]=head[x],head[x]=tot,val[tot]=z;}
void dfs(int pos,int pre)
{
	siz[pos]=1;
	int i,j,k;
	for(i=head[pos];i;i=nxt[i])
		if(to[i]!=pre)
		{
			dfs(to[i],pos);
			for(j=siz[pos];~j;--j)
				for(k=siz[to[i]];~k;--k)
					f[pos][j+k]=max(f[pos][j+k],f[pos][j]+f[to[i]][k]+1ll*(k)*(m-k)*val[i]+1ll*(siz[to[i]]-k)*(n-siz[to[i]]-(m-k))*val[i]);
			siz[pos]+=siz[to[i]];
		}
	return;
}
int main()
{
	int x,y,z;
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;++i) scanf("%d%d%d",&x,&y,&z),ae(x,y,z),ae(y,x,z);
	dfs(1,0);
	printf("%lld\n",f[1][m]);
	return 0;
}