记录编号	256121	评测结果	AAAAAAAAAAAAA
题目名称	[Ural 1018] 二叉苹果树	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2016-04-29 11:51:04	内存使用	0.39 MiB

#include<cstdio>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("ecappletree.in","r",stdin);freopen("ecappletree.out","w",stdout);chul();Cu;
using namespace std;
//designed by New_Beeؼ 
struct op{
	int lson,rson;
	op(){
		lson=rson=0;
	}
};
const int maxn=105;
int n,q;
op apt[maxn];
bool flag[maxn];
bool sk[maxn][maxn];
int nap[maxn][maxn];
int f[maxn][maxn];
void chul();
int getmax(int,int);
void build(int);
int DP(int,int);
void mem();
int main(){
	Begin;
}
void chul(){
	mem();
	scanf("%d%d",&n,&q);
	for(int i=1;i<n;i++){
		int a,b,numap;
		scanf("%d%d%d",&a,&b,&numap);
		sk[a][b]=sk[b][a]=1;
		nap[a][b]=nap[b][a]=numap;
	}
	build(1);
	DP(1,q);
	printf("%d",f[1][q]);
}
void mem(){
	for(int i=0;i<maxn;i++){
		for(int j=0;j<maxn;j++)sk[i][j]=nap[i][j]=f[maxn][maxn]=0;
		flag[i]=0;
	}
}
void build(int rt){
	flag[rt]=1;
	for(int i=1;i<=n;i++){
		if(sk[rt][i]==1&&flag[i]!=1){
			if(apt[rt].lson==0)apt[rt].lson=i;
			else apt[rt].rson=i;
			build(i);
		}
	}
}
int DP(int rt,int nt){
	if(rt==0||nt==0)return 0;
	if(f[rt][nt]!=0)return f[rt][nt];
	f[rt][nt]=getmax(f[rt][nt],DP(apt[rt].lson,nt-1)+nap[rt][apt[rt].lson]);
	f[rt][nt]=getmax(f[rt][nt],DP(apt[rt].rson,nt-1)+nap[rt][apt[rt].rson]);
	int t=nap[rt][apt[rt].lson]+nap[rt][apt[rt].rson];
	for(int k=0;k<=nt-2;k++){
		f[rt][nt]=getmax(f[rt][nt],DP(apt[rt].lson,k)+DP(apt[rt].rson,nt-2-k)+t);
	}
	return f[rt][nt];
}
int getmax(int x,int y){
	if(x>y)return x;
	return y;
}