题目描述
有一棵点数为 N 的树，树边有边权。给你一个在 0~ N 之内的正整数 K ，你要在这棵树中选择 K个点，将其染成黑色，并将其他 的N-K个点染成白色 。 将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。
输入输出格式
输入格式：
第一行包含两个整数 N, K 。接下来 N-1 行每行三个正整数 fr, to, dis ， 表示该树中存在一条长度为 dis 的边 (fr, to) 。输入保证所有点之间是联通的。
输出格式：
输出一个正整数，表示收益的最大值。
输入输出样例
输入样例#1： 复制
3 1
1 2 1
1 3 2
输出样例#1： 复制
3
说明
对于 100% 的数据， 0<=K<=N <=2000
求染色后黑点间距离之和加白点间距离之和之和的最大值，考虑去掉后效性的方法
对于每一棵子树来说，其对于答案的贡献其实只有子树内同色点距离和，和黑点到子树根的距离和\(*\)子树外黑色点的个数+白色点到子树根的距离和\(*\)子树外白色点的个数，就可以转移了，\(f[i][j]\) 表示\(i\)及其子树内染黑\(j\)个点能都得到的最大收益。
由于子树根节点的颜色对于其子树的答案是没有贡献的（…） 所以把根节点染黑的情况就是\(f[i][j]=f[i][j-1]\)(…)
然后直接转移就行了啊
需要注意的是因为一棵子树都是必须要选的，是不能直接不选的，直接更新会对后面的更新在成影响，所以先建一个\(g\)数组在每一次用一棵新子树跟新答案时记录新答案，然后直接用其更新\(f\)数组的值即可
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;long long i,m,n,j,k,ver[10001],head[10001],nex[10001],edge[10001],z,cnt,x,y,f[2001][2001],g[2001],size[10001];void add(long long x,long long y,long long z)
{
cnt+=1;
ver[cnt]=y;
nex[cnt]=head[x];
head[x]=cnt;
edge[cnt]=z;
}void dfs(long long now,long long fa)
{
f[now][0]=0;
for(int i=head[now];i;i=nex[i])
{
int t=ver[i];
if(t==fa) continue;
dfs(t,now);
memset(g,-0x3f,sizeof(g));
size[now]+=size[t];for(long long j=min(size[now],m);j>=0;j--)
for(int l=0;l<=min(size[t],j);l++)
g[j]=max(g[j],f[now][j-l]+f[t][l]+edge[i]*l*(m-l)+edge[i]*(size[t]-l)*(n-m-size[t]+l));for(int j=0;j<=min(size[now],m);j++) f[now][j]=g[j];
}
size[now]+=1;
if(size[now]==1) f[now][1]=0;
f[now][size[now]]=f[now][size[now]-1];
for(int i=size[now];i>=1;i--) f[now][i]=max(f[now][i],f[now][i-1]);
}int main()
{
scanf("%lld%lld",&n,&m);
memset(f,-0x3f,sizeof(f));
for(i=1;i<n;i++)
{
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs(1,0);
printf("%lld",f[1][m]);
}
（话说这道题作为一道连数据范围都没有的题，会爆int是不是有点过分啊啊啊啊啊 (ノ>д<)ノ彡┻━┻
