「HAOI2015」树上染色

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

一道经典的树形 DP。

$f _{i,j}$ 表示以 $i$ 为根的子树将 $j$ 个点涂成黑色的最大值。

考虑子树内的边对答案贡献的最大值。

整棵树有 $k$ 个黑点，则有 $n-k$ 个白点，子树中有 $m$ 个黑点，则有 $size _{v}-m$ 个白点，子树外有 $k-m$ 个黑点，有 $n-k-size _{v}+m$ 个白点。

状态转移方程为：

$$f _{u,j}=\max(f _{u,j-m}+f _{v,m}+(m\times (k-m)+(size _{v}-m)\times(n-k-size _{v}+m))\times w(u,v))(v\in S _{u})$$

即子树内黑乘子树外黑加上子树内白乘子树外白后再乘以边权，这就是该子树的贡献。

最后用刷表法转移即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=2010;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int n,k;
int head[maxn],cnt,size[maxn];
long long f[maxn][maxn],g[maxn];
struct node
{
	int next;
	int to;
	int num;
}e[maxn<<1];
void add(int from,int to,int num)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	e[cnt].num=num;
	head[from]=cnt;
}
void dfs(int u,int fa)
{
	size[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa)
			continue;
		dfs(v,u);
		memset(g,0,sizeof(g));
		for(int j=size[u];j>=0;j--)
			for(int m=0;m<=size[v];m++)
				g[j+m]=max(g[j+m],f[u][j]+f[v][m]+1ll*(m*(k-m)+(size[v]-m)*(n-k-size[v]+m))*e[i].num);
		for(int j=0;j<=size[u]+size[v];j++)
			f[u][j]=g[j];
		size[u]+=size[v];
	}
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	dfs(1,0);
	printf("%lld",f[1][k]);
	return 0;
}