Description:

点数为 $N$ 的树，树边有边权。在这棵树中选择 $K$ 个点，将其染成黑色，并将其他的 $N-K$ 个点染成白色 。问黑点两两之间的距离加上白点两两之间的距离的和最大值是多少。

$1\le K\le N\le 2000$

Solution:

由于收益在边上，所以定义 $f[i][j]$ 表示以 $i$ 为根的子树中有 $j$ 个黑点，所有边的收益已经计算完的收益最大值。转移时对于一条父子边 $(fa,to)$ ，经过它的次数为 $(K-j)\times j+(siz_{to}-j)\times((N-K)-(siz_{to}-j))$ ， $O(N^3)$ 跑背包就过了。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

inline int read()

{

	int res = 0;

	char c = getchar();

	while(c < '0' || c > '9')c = getchar();

	while('0' <= c && c <= '9')

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

} 

#define MAXN 2010

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b,int c)

{

	++edgenum;

	e[edgenum].to = b;

	e[edgenum].v = c;

	e[edgenum].nxt = lin[a];

	lin[a] = edgenum;

	return;

}

long long f[MAXN][MAXN];

int siz[MAXN];

bool v[MAXN];

void dp(int k)

{

	siz[k] = 1;

	v[k] = true;

	f[k][0] = 0;

	f[k][1] = 0;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!v[e[i].to])

		{

			dp(e[i].to);

			siz[k] += siz[e[i].to];

			for(register int j = m;j >= 0;--j)

			{

				for(register int l = 0;l <= j && l <= siz[e[i].to];++l)

				{

					f[k][j] = max(f[k][j],f[k][j - l] + f[e[i].to][l] + (long long)(m - l) * (long long)l * (long long)e[i].v + (long long)(siz[e[i].to] - l) * (long long)((n - m) - (siz[e[i].to] - l)) * (long long)e[i].v);

				}

			}

		}

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b,c;

	for(register int i = 1;i < n;++i)

	{

		a = read();b = read();c = read();

		add(a,b,c);add(b,a,c);

	}

	memset(v,false,sizeof(v));

	memset(f,0xc0,sizeof(f));

	dp(1);

	printf("%lld\n",f[1][m]);

	return 0;

}