记录编号	544248	评测结果	AAAAAAAAAAAAA
题目名称	[Ural 1018] 二叉苹果树	最终得分	100
用户昵称	ShallowDream雨梨	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2019-10-15 19:47:22	内存使用	17.54 MiB

	#include<bits/stdc++.h> 
	#define bianli for(int i=head[x];i;i=a[i].next)
	using namespace std;
	const int maxn=1005;
	int f[maxn][maxn],size[maxn],tot,head[maxn];
	struct road{int v,to,next;}a[maxn*2];
	void add(int x,int y,int z){
	a[++tot].v=z;a[tot].to=y;
	a[tot].next=head[x];head[x]=tot;}
	void dfs(int x,int fa){
		size[x]=1;
		bianli{
		int to=a[i].to;
		if(to==fa)continue;
		dfs(to,x);
		size[x]+=size[to];
		for(int j=size[x];j;j--)
		for(int k=min(j-1,size[to]);k>=0;k--)
		f[x][j]=max(f[x][j],f[x][j-k-1]+a[i].v+f[to][k]);
		}}
	int main(){
	freopen("ecappletree.in","r",stdin);
	freopen("ecappletree.out","w",stdout);
    int n,k,q,w,e;
    cin>>n>>k;
    for(int i=1;i<n;i++){cin>>q>>w>>e;
    add(q,w,e);add(w,q,e);}
    dfs(1,0);
    cout<<f[1][k];
	return 0;
	}