【题意】给定n个点的带边权树，要求将k个点染成黑色，使得 [ 黑点的两两距离和+白点的两两距离和 ] 最大。n<=2000。
【算法】树上背包
【题解】设f[i][j]表示子树i中有j个黑点对答案的贡献（包括点 i 到父亲的边 p ），由于边p的贡献只和 j 有关，所以最后再统计。
所以做树上背包即可，注意这题特殊在f[x][0]≠0，所以初始f[x][k]+=f[y][0]，然后不要把0作为物品。
最后统计边p的贡献：w[p] *（子树内黑点*子树外黑点+子树内白点*子树外白点）。
常数问题：要尽可能避免枚举无用状态，不然常数太大了，优化见代码。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=,inf=0x3f3f3f3f;
struct edge{int v,w,from;}e[maxn*];
int first[maxn],tot,n,K,sz[maxn];
ll f[maxn][maxn];
void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}
ll max(ll a,ll b){return a<b?b:a;}
void dfs(int x,int fa,int w){
for(int i=;i<=K;i++)f[x][i]=-inf;
sz[x]=;
for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){
dfs(e[i].v,x,e[i].w);
sz[x]+=sz[e[i].v];
for(int k=min(sz[x],K);k>=;k--){
f[x][k]+=f[e[i].v][];//
for(int j=min(k,sz[e[i].v]);j>=;j--)if(f[x][k-j]>-inf){//
f[x][k]=max(f[x][k],f[x][k-j]+f[e[i].v][j]);
}else break;
}
}
for(int i=;i<=K;i++)if(f[x][i]>-inf)f[x][i]+=1ll*w*(1ll*i*(K-i)+1ll*(sz[x]-i)*(n-K-sz[x]+i));
}
int main(){
scanf("%d%d",&n,&K);
for(int i=;i<n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
insert(u,v,w);insert(v,u,w);
}
dfs(,,);
printf("%lld",f[][K]);
return ;
}