记录编号	543557	评测结果	AAAAAAAAAAAAA
题目名称	[Ural 1018] 二叉苹果树	最终得分	100
用户昵称	leon	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2019-10-06 10:46:13	内存使用	13.84 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<deque>
using namespace std; 
int n,m,tot,f[210][210],head[210],sz[210];
struct dd{
	int to,next,from,v;
}a[210*2];
void add(int x1,int x2,int x3){
	tot++;
	a[tot].to=x2;
	a[tot].from=x1;
	a[tot].v=x3;
	a[tot].next=head[x1];
	head[x1]=tot; 
} 
void dfs(int x,int fa){
    for(int i=head[x];i;i=a[i].next){
        int to=a[i].to;if(to==fa)continue;
        dfs(to,x);
		sz[x]+=sz[to]+1;
        for(int j=min(sz[x],m);j;--j) 
            for(int k=min(j-1,sz[to]);k>=0;--k)    
                f[x][j]=max(f[x][j],f[x][j-k-1]+f[to][k]+a[i].v);
    }
}
int main(){
	freopen("ecappletree.in","r",stdin);
	freopen("ecappletree.out","w",stdout);
    int xx,yy,zz;
    cin>>n>>m;
    for(int i=1;i<n;i++){
		cin>>xx>>yy>>zz;
		add(xx,yy,zz);
		add(yy,xx,zz);
    }
    dfs(1,0);
    cout<<f[1][m];

	return 0;
}