记录编号	160534	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上染色	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.096 s
提交时间	2015-04-28 11:04:43	内存使用	66.33 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define UseFREAD
#ifdef UseFREAD
#define getc() *(file_ptr++)
#define FreadLenth 5000000
char CHARPOOL[FreadLenth], *file_ptr = CHARPOOL;
#else
#define getc() getchar() 
#endif
#ifdef DEBUG
#include <sys/timeb.h>
timeb SysTp;
#endif
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 2003;
typedef long long LL;
#include <vector>
struct Edge{int to, w;};
vector<Edge> adj[maxn];

LL f[maxn][maxn], S[maxn][maxn];
int N, K, size[maxn];

inline void UPD(LL &a, const LL &b){if(a < b)a = b;}

void dfs(int cur, int p, int w){
	vector<Edge>::iterator it;
	int i, j, to;
	size[cur] = 1;
	for(it = adj[cur].begin();it != adj[cur].end();++it)if((to = (*it).to) != p){
		dfs(to, cur, (*it).w);
		for(i = min(size[cur], K);i >= 0;--i)for(j = min(size[to], K - i);j >= 0;--j)
			UPD(S[cur][i + j], S[cur][i] + f[to][j]);
		size[cur] += size[to];
	}
	for(i = size[cur];i >= 0;--i)
		f[cur][i] = S[cur][i] + (LL)w * (i * (K - i) + (N - K - size[cur] + i) * (size[cur] - i));
}

inline void work(){
	getd(N), getd(K);
	int i, a, b, c;
	for(i = 1;i < N;++i){
		getd(a), getd(b), getd(c);
		adj[a].push_back((Edge){b, c});
		adj[b].push_back((Edge){a, c});
	}
	dfs(1, 0, 0);
	printf("%lld\n", f[1][K]);
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);ftime(&SysTp);
	size_t Begin_sec = SysTp.time, Begin_mill = SysTp.millitm;
#elif !defined ONLINE_JUDGE
	SetFile(haoi2015_t1);
#endif

#ifdef UseFREAD
	fread(file_ptr, 1, FreadLenth, stdin);
#endif

	work();

#ifdef DEBUG
	ftime(&SysTp);
	printf("\n%.3lf sec \n", (SysTp.time - Begin_sec) + (SysTp.millitm - Begin_mill) / 1000.0);
#endif
	return 0;
}