P3177 [HAOI2015] 树上染色

有一棵点数为 n 的树，树边有边权。

给你一个在 0∼n之内的正整数 k，

选择 k个点，将其染成黑色，并将其他 的 n−k个点染成白色。

你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问受益最大值是多少

  考虑一条边z（x->y) 对答案的贡献 ORZ,

 f[x][j]= f[x][j-k]+f[y][k] + z*j*(m-j) +z*(sz[y]-j)  *( n-sz[y] -(m-j) )

#include <bits/stdc++.h>
using namespace std ;
 const int N=2003,M=2003*2;
 #define int long long
 int nxt[M],go[M],hd[N],w[M],all;
 
 int n,m,sz[N];
 int f[N][N];
 
 void add(int x,int y,int z){
 	go[++all]=y,nxt[all]=hd[x],hd[x]=all;
 	w[all]=z;
 }
 
 void dfs(int x,int father){
 	sz[x]=1;
 	memset(f[x],-1,sizeof f[x]);
 	f[x][0]=f[x][1]=0;
 	
 	for(int i=hd[x];i;i=nxt[i]){
 		int y=go[i]; if(y==father) continue;
 		dfs(y,x);
 		sz[x]+=sz[y];
 	}	
 	for(int i=hd[x];i;i=nxt[i]){
 		int y=go[i]; if(y==father) continue;
 		
 		for(int j=min(m,sz[x]);j>=0;j--)
 		 for(int k=0;k<=min(j,sz[y]);k++) if(f[x][j-k]!=-1)
 		f[x][j]= max(f[x][j],f[x][j-k]+f[y][k]+
 		w[i]*k*(m-k)+ w[i]*(sz[y]-k)*(n-sz[y]-m+k));
 	}
 }
 signed main(){
 	cin>>n>>m;
 	int x,y,z;
 	for(int i=1;i<n;i++) 
 		cin>>x>>y>>z,add(x,y,z),add(y,x,z);
 	dfs(1,0);
 	cout<<f[1][m]<<endl;
 }