一道非常好的树形DP。
状态：\(dp[u][n]\)为u的子树选n个黑点所能得到的收益最大值。
则最终的结果就是\(dp[root][k],\)\(root\)可以为任何值，为了方便，使\(root=1\)
然后考虑怎么状态转移，状态转移一般要从方程和边界入手，考虑用背包的思想，得到方程：
\[ dp[now][j]=max(dp[now][j], dp[now][j-l]+dp[to][l]+子树选l个黑点的贡献)\]
\((0<=j<=min(k, size[now]), 0<=l<=min(j,size[to]))\)
接下来问题转化为如何求他们的贡献
根据题意，贡献就是（黑点的距离和+白点的距离和）= \(e[i].len * ( (k - l) * l + (siz[to] - l) * (n - k - siz[to] + l) )\)
且这只能由\(dp[now][j-l]\)已被更新的情况下才可以更新。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k, cnt, root, lin[3010], vis[3010], siz[3010], dp[3010][3010];//每个点的最短路
struct edg {
int to, nex, len;
}e[4001011];
inline void add(int f, int t, int l)
{
e[++cnt].to = t;
e[cnt].len = l;
e[cnt].nex = lin[f];
lin[f] = cnt;
}
void init(int now, int fa, int de)
{
siz[now] = 1;
for (int i = lin[now]; i; i = e[i].nex)
{
int to = e[i].to;
if (to == fa) continue;
init(to, now, de + 1);
siz[now] += siz[to];
}
return;
}
void dfs(int now, int fa)
{
dp[now][0] = dp[now][1] = 0;//dp[u][i]表示u该节点的子树中选择i个黑色节点的最大贡献。
for (int i = lin[now]; i; i = e[i].nex)
{
int to = e[i].to;
if (to == fa) continue;
dfs(to, now);
}//此时他的子树都已经搜索完了。
for (int i = lin[now]; i; i = e[i].nex)
{
int to = e[i].to;
if (to == fa) continue;
for (int j = min(k, siz[now]); j >= 0; j--)
for (int l = 0; l <= min(j, siz[to]); l++)//01背包
{
int ha = e[i].len * ( (k - l) * l + (siz[to] - l) * (n - k - siz[to] + l) );//to节点选择l个黑色节点
if (dp[now][j - l] != -1)
dp[now][j] = max(dp[now][j], dp[now][j - l] + dp[to][l] + ha);//对它的所有贡献
}
}
}
signed main()
{
memset(dp, -1, sizeof(dp));
scanf("%lld%lld", &n, &k);
for (int i = 1, fr, to, dis; i < n; i++)
scanf("%lld%lld%lld", &fr, &to, &dis), add(fr, to, dis), add(to, fr, dis);
init(1, -1, 1);//对树初始化.
dfs(1, -1);
printf("%lld", dp[1][k]);//必须染有k个黑点才能满足条件,多了少了都不行。
return 0;
}