记录编号	160715	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上染色	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.149 s
提交时间	2015-04-29 10:47:46	内存使用	31.18 MiB

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int L_N=2000+10;
int N,K;
vector<PII> G[L_N];
LL f[L_N][L_N];
int size[L_N];

LL calc_val(int k,int tk){
	return 1ll*k*(tk-k);
}

LL tf[L_N];
void dp(int u,int fa){
	size[u]=1;
	f[u][0]=f[u][1]=0;
	
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i].first,c=G[u][i].second; if(v==fa) continue;
		dp(v,u);
		
		for(int vk=0;vk<=size[v];vk++){
			for(int uk=0;uk<=size[u] && uk+vk<=K;uk++){
				LL tmp=(calc_val(vk,K)+calc_val(size[v]-vk,N-K))*c+f[v][vk];
				tf[vk+uk]=max(tf[vk+uk],f[u][uk]+tmp);
			}
		}
		
		for(int k=0;k<=K;k++){
			f[u][k]=tf[k];
			tf[k]=0;
		}
		
		size[u]+=size[v];
	}
	
	//for(int i=0;i<=K;i++){
	//	printf("f[%d][%d]=%d\n",u,i,f[u][i]);
	//}
}
int main(){
	freopen("haoi2015_t1.in","r",stdin);
	freopen("haoi2015_t1.out","w",stdout);
	scanf("%d %d",&N,&K);
	if(K>(N/2)) K=N-K;
	for(int i=1;i<N;i++){
		int u,v,c; scanf("%d %d %d",&u,&v,&c);
		G[u].push_back(PII(v,c));
		G[v].push_back(PII(u,c));
	}
	dp(1,0);
	printf("%lld\n",f[1][K]);
	return 0;
}