记录编号	389081	评测结果	AAAAAAAAAAAAA
题目名称	[Ural 1018] 二叉苹果树	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2017-03-30 16:36:01	内存使用	0.52 MiB

/*kZime*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <algorithm>

using namespace std;
/*-----------------------------------------------------------------------------*/
inline void File_Read() {
#ifndef MYLAB
	freopen("ecappletree.in", "r", stdin);
	freopen("ecappletree.out", "w", stdout);
#else
	freopen("in.txt", "r", stdin);
#endif
}

inline int get_num() {
	int k = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar())if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}

int n, q, tot[233], dp[233][233], cnt, head[233];

struct edge{
	int fr, to, ne, w;
	edge(){;}
	inline edge(int fr_, int to_, int w_  ,int ne_) {
		fr = fr_;
		to = to_;
		ne = ne_;
		w  = w_ ;
	}
}e[233];

inline void add(int fr, int to, int w) {
	e[++cnt] = edge(fr, to, w, head[fr]), head[fr] = cnt;
	e[++cnt] = edge(to, fr, w, head[to]), head[to] = cnt;
}

void dfs(int now, int fa) {
	tot[now] = 1;
	for(int i = head[now];i; i = e[i].ne) {
		int to = e[i].to;
		if(to == fa) continue;
		dfs(to, now);
		tot[now] += tot[to];
	}
	
	for(int i = head[now];i; i = e[i].ne) {
		int to = e[i].to;
		if(to == fa) continue;
		for(int j = tot[now]; j > 1; --j) {
			for(int k = 1; (k < j) && (k <= tot[to]); ++k) {
				dp[now][j] = max(dp[now][j], dp[now][j - k] + dp[to][k] + e[i].w);
			}
		}
	}
}

int main() {
	File_Read();
	n = get_num();
	q = get_num();
	for(int i = 1; i < n; i++) {
		int a = get_num();
		int b = get_num();
		int c = get_num();
		add(a, b, c);
	}

//	for(int i = 1; i <= cnt; i++) {
//		printf("%d  %d  %d  %d\n", e[i].fr, e[i].to, e[i].w, e[i].to);
//	}
	dfs(1, 0);

	printf("%d", dp[1][q + 1]);


	return 0;
}