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

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 2e3+5;
typedef long long LL;
int n, K;

inline int get_num() {
	int ans = 0;
	char tmp = getchar();
	while(tmp < '0' || tmp > '9') tmp = getchar();
	while(tmp <= '9' && tmp >= '0') {
		ans = ans*10 + tmp - '0';
		tmp = getchar();
	} 
	return ans;
}

struct edge {
	int to, ne, v;
	inline edge() {}
	inline edge(int to_, int ne_, int v_) {to = to_, ne = ne_, v = v_;}
}e[maxn*2];
int head[maxn], tot;
inline void add_edge(int fr, int to, int v) {
	e[++tot] = edge(to, head[fr], v); head[fr] = tot;
	e[++tot] = edge(fr, head[to], v); head[to] = tot;
}

int size[maxn];
LL f[maxn][maxn];
LL add[maxn];
bool vis[maxn];

inline void read() {
	n = get_num();
	K = get_num();
	for(int i = 1; i <= n-1; i++) {
		int a, b, c;
		a = get_num();
		b = get_num();
		c = get_num();
		add_edge(a, b, c);
	} 
} 

inline void dp(int now) {
	vis[now] = true;
	size[now] = 1;
	for(int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if(vis[to]) continue;
		dp(to);
		
		for(int use = 0; use <= size[to]; use++) {//当前子树使用黑点数 
			for(int le = 0; le <= size[now] && le + use <= K; le++) {//当前父节点使用节点数 
				LL tmp = (1ll*use*(K-use) + 1ll*(size[to]-use) * (n-(K-use)-size[to]))*e[i].v + f[to][use];//当前边的总增量+子节点的增量
				add[use+le] = max(add[use+le], f[now][le]+tmp);//父节点使用总数取最大值 
			}
		}
		
		/*for(int j = 0; j <= min(K, size[now]); j++) {//给多少个黑点来染 
			for(int k = 0; k <= min(j, size[to]); k++) {//染多少个黑点 
				LL tmp = (k*(K-k) + (size[to]-k) * (n-(K-k)-size[to]))*e[i].v + f[to][k];//当前边的总增量+子节点的增量
				add[j] = max(add[j], f[now][j-k]+tmp);
				//在最大加j的情况下的最大值为对应每一个不加k的状态加上当前状态之后的值和之前比对的最大值 
			}
		}*/
		for(int j = 0; j <= K; j++) {
			f[now][j] = add[j];
			add[j] = 0;
		}
		size[now] += size[to];
	}
}

int main() {
	freopen("haoi2015_t1.in", "r", stdin);
	freopen("haoi2015_t1.out", "w", stdout); 
	read();
	dp(1);
	printf("%lld", f[1][K]);
}