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

#include<cstdio>
#include<iostream>
const int maxn=105;
using namespace std;
struct edge
{
	int fr,to,va;
	edge *nt;
	edge(){fr=to=va=0;nt=NULL;}
}*e[maxn];
inline int get();
inline edge *add(int fr,int to,int va);
int dfs(edge *now);
int n,m;
int a,b,c;
int f[maxn][maxn];
bool jud[maxn];
int main()
{
	freopen("ecappletree.in","r",stdin);
	freopen("ecappletree.out","w",stdout);
	n=get(),m=get();
	for(int i=1;i<n;i++)
	{
		a=get(),b=get(),c=get();
		e[a]=add(a,b,c);
		e[b]=add(b,a,c);
	}
	jud[1]=true;
	dfs(e[1]);
	printf("%d",f[1][m]);
	return 0;
}
int dfs(edge *now)
{
	int siz=0,fr=now->fr;
	for(;now;now=now->nt)
	{
		if(jud[now->to])continue;
		jud[now->to]=true;
		siz+=dfs(e[now->to])+1;
		for(int i=min(m,siz);i>=1;i--)
		{
			for(int j=min(i,m);j>=1;j--)
			{
				f[fr][i]=max(f[fr][i],f[fr][i-j]+f[now->to][j-1]+now->va);
			}
		}
	}
	return siz;
}
inline edge *add(int fr,int to,int va)
{
	edge *p=new edge();
	p->fr=fr;p->to=to;p->va=va;
	p->nt=e[fr];
	return p;
}
inline int get()
{
	int t=0;char c=getchar(),j=1;
	while(!isdigit(c))
	{
		if(c=='-')j=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		t=(t<<3)+(t<<1)+c-'0';
		c=getchar();
	}
	return j*t;
}