Description
有一棵点数为\(N\)的树，树边有边权。给你一个在\(0-N\)之内的正整数\(K\)，你要在这棵树中选择\(K\)个点，将其染成黑色，并将其他的\(N-K\)个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。
Input
第一行包含两个整数\(N,K\)。
接下来\(N-1\)行每行三个正整数\(fr, to, dis\)，表示该树中存在一条长度为\(dis\)的边\((fr, to)\)。输入保证所有点之间是联通的。
Output
输出一个正整数，表示收益的最大值。
Sample Input
3 1
1 2 1
1 3 2
Sample Output
3
HINT
对于\(100\%\)的数据，\(0 \le K \le N \le 2000\)。
一道很好的树形dp题。\(f_{i,j}\)表示以\(i\)为根的子树中染\(j\)个黑点的最大收益，那么问题就来了，应该怎么转移？
假设我们此时已经dp到\(now\)这个跟，试着更新\(f_{now,j}\)，现在用其儿子\(c\)来更新。假设连接\(now\)和\(c\)的边权值\(dis\)，枚举\(f_{c,k}\)，之后就计算此边贡献即可。黑点这条边经过了\((K-k) \times k\)次（所有黑点，并不只是\(now\)子树中），故贡献\((K-k) \times k \times dis\)。白点也这样算即可。故转移方程为
\[f_{now,j} = max(f_{now,j},f_{now,j-k}+f_{c,k}+(K-k) \times k \times dis+(N-K-(size-k)) \times (size-k) \times dis)
\]
\]
其中\(size\)为\(c\)的子树大小。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define maxn (2010)
typedef long long ll;
int cnt,N,K,len[maxn*2],next[maxn*2],toit[maxn*2],side[maxn]; ll f[maxn][maxn];
inline void add(int a,int b,int c) { next[++cnt] = side[a]; side[a] = cnt; toit[cnt] = b; len[cnt] = c; }
inline void ins(int a,int b,int c) { add(a,b,c); add(b,a,c); }
inline void upd(ll &a,ll b) { a = max(a,b); }
inline int dfs(int now,int fa)
{
int sz = 1;
memset(f[now],128,sizeof(f[now])); f[now][0] = f[now][1] = 0;
for (int i = side[now];i;i = next[i])
{
if (toit[i] == fa) continue;
int num = dfs(toit[i],now);
for (int j = min(K,sz += num);j >= 0;--j)
for (int k = 0;k <= num&&k <= j;++k)
upd(f[now][j],((ll)(K-k)*(ll)k+(ll)(N-K-(num-k))*(ll)(num-k))*(ll)len[i]+f[toit[i]][k]+f[now][j-k]);
}
return sz;
}
int main()
{
freopen("4033.in","r",stdin);
freopen("4033.out","w",stdout);
scanf("%d %d",&N,&K);
for (int i = 1,a,b,c;i < N;++i) scanf("%d %d %d",&a,&b,&c),ins(a,b,c);
dfs(1,0);
printf("%lld",f[1][K]);
fclose(stdin); fclose(stdout);
return 0;
}