记录编号	381352	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上染色	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.817 s
提交时间	2017-03-11 13:33:07	内存使用	41.91 MiB

/*kZime*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long
#define MAXN 2333
using namespace std;

ll sz[MAXN], n, k, dp[MAXN][MAXN];
vector<int> to[MAXN], we[MAXN];
inline ll read() {
	ll k = 0; char c = getchar();
	for(; !isdigit(c); c = getchar());
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k;
} 

void dfs(int u, int fa) {
	sz[u] = 1;
	memset(dp[u], -1, sizeof(dp[u]));
	dp[u][0] = dp[u][1] = 0;
	
	for(int i = 0; i < to[u].size(); i++) {
		int v = to[u][i];
		if(v == fa)continue;
		else{
			dfs(v, u);
			sz[u] += sz[v];
		}
	}
	
	for(int i = 0; i < to[u].size(); i++) {
		int v = to[u][i];
		int w = we[u][i];
		if(v == fa)continue;
		else{
			for(ll i = min(k, sz[u]); i >= 0; i--) {
				for(ll j = 0; j <= min(i, sz[v]); j++) {
					if( ~dp[u][i-j] ) {
        			    ll val = (ll) j * ( k - j ) * w + (ll) ( sz[v] - j ) * ( n - k + j - sz[v] ) * w;
       			 	  	dp[u][i] = max( dp[u][i], dp[u][i-j] + dp[v][j] + val );
        			}
				}
			}
		}
	}
}

int main() {
#ifndef LOCAL
	freopen("haoi2015_t1.in", "r", stdin);
	freopen("haoi2015_t1.out", "w", stdout);
#else 
	freopen("in.txt", "r", stdin);
#endif
	n = read();
	k = read();
	
	for(int i = 1; i < n; i++) {
		int x = read();
		int y = read();
		int z = read();
		we[x].push_back(z);
		to[x].push_back(y);
		we[y].push_back(z);
		to[y].push_back(x); 
	}
	
	dfs(1, 0);
	
	printf("%lld",dp[1][k]);
		
}