记录编号	390978	评测结果	AAAAAAAAAAAAA
题目名称	[Ural 1018] 二叉苹果树	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2017-04-04 19:51:18	内存使用	0.36 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define is_num(tmp) (tmp<='9' and tmp>='0')

const int MAXN = 110;

const inline int in(void){
	char tmp = getchar();
	int res = 0;
	while(!(is_num(tmp) || tmp == '-')) tmp = getchar();
	while(is_num(tmp))
		res = (res<<1) + (res<<3) + (tmp^48),
		tmp = getchar();
	return res;
}

struct EDGE{
	int fr, to;
	int ne, v;
	
	EDGE(){;}
	EDGE(const int& _fr, const int& _to, const int& _ne, const int& _v){
		fr = _fr, to = _to;
		ne = _ne, v = _v;
	}
};

EDGE edge[MAXN<<1];
int head[MAXN], tot;
int cnt[MAXN], f[MAXN][MAXN];
int N, Q;

const inline void add_edge(const int& fr, const int& to, const int& v);
void dfs(const int& now, const int& fa);

int main(){
#ifndef LOCAL
	freopen("ecappletree.in", "r", stdin);
	freopen("ecappletree.out", "w", stdout);
#endif
	N = in(), Q = in();
	for(int i = 1, a, b, c; i < N; ++i){
		a = in(), b = in(), c = in();
		add_edge(a, b, c);
	}
	
	dfs(1, 0);
#ifdef debug
	for(int i = 0; i <= cnt[1]; ++i){
		printf("%d ", f[1][i]);
	}
#endif
	
	printf("%d", f[1][Q]);
	return 0;
}

const inline void add_edge(const int& fr, const int& to, const int& v){
	edge[++tot] = EDGE(fr, to, head[fr], v), head[fr] = tot;
	edge[++tot] = EDGE(to, fr, head[to], v), head[to] = tot;
	return ;
}

void dfs(const int& now, const int& fa){
	int to;
	int ls = 0, rs = 0, lv = 0, rv = 0;
	for(int i = head[now]; i; i = edge[i].ne){
		to = edge[i].to;
		if(to == fa) continue;
		else if(!ls) ls = to, lv = edge[i].v;
		else if(!rs) rs = to, rv = edge[i].v;
		dfs(to, now);
		cnt[now] += cnt[to];
	}
	
	if(ls) ++cnt[now];
	if(rs) ++cnt[now];
	
	if(ls && rs){
		f[now][1] = max(lv, rv);
		for(int i = 2; i <= cnt[now]; ++i){
			for(int j = max(0, i-cnt[rs]-1), end = min(i, cnt[ls] + 1); j <= end; ++j){
				if(i == j)f[now][i] = max(f[now][i], f[ls][j-1] + lv);
				else if(!j) f[now][i] = max(f[now][i], f[rs][i-1] + rv);
				else f[now][i] = max(f[now][i], f[ls][j-1] + lv + f[rs][i - j - 1] + rv);
			}
		}
	}
	else if(ls){
		f[now][1] = lv;
		for(int i = 2; i <= cnt[now]; ++i){
			f[now][i] = f[ls][i-1] + lv;
		}
	}
	
	return ;
}