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

#include<bits/stdc++.h>
using namespace std;

int n,q,app[109][109],ans=0;
int x,y,z,s[109];
int f[109][109],fa[109],si[109];
vector<int>v[109];

void init(){
	cin>>n>>q;
	for(int i=1;i<n;i++){
		cin>>x>>y>>z;
		app[x][y]=app[y][x]=z;
		v[x].push_back(y);
		v[y].push_back(x);
	}
}

void dfs(int x){
	int l=0,r=0;si[x]=1;
	for(int i=0;i<v[x].size();i++){
		if(v[x][i]!=fa[x]){
			if(!l)l=v[x][i];
			else r=v[x][i];
			s[v[x][i]]+=app[x][v[x][i]];
			fa[v[x][i]]=x;
			dfs(v[x][i]);
			si[x]+=si[v[x][i]];
		}
	}
	if(l&&r){
		for(int i=0;i<=si[x];i++){
			for(int j=0;j<=i;j++){
				f[x][i+1]=max(f[x][i+1],f[l][j]+f[r][i-j]+s[x]);
			}
		}
	}else{
		f[x][1]=s[x];
	}
}

int main(){
	freopen("ecappletree.in","r",stdin);
	freopen("ecappletree.out","w",stdout);
	ios::sync_with_stdio(false);
	init();
	dfs(1);
	cout<<f[1][q+1]<<endl;
	return 0;
}