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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=210;
namespace mine{
	int c,x,a[110],i,j;
	bool neg;
	inline int getint(){
		x=neg=0;
		do c=getchar();while(c==' '||c=='\n'||c=='\r'||c=='\t');
		if(c=='-'){
			neg=true;
			c=getchar();
		}
		for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
		if(neg)return -x;
		return x;
	}
	inline int fgeti(FILE* fin){
		x=neg=0;
		do c=fgetc(fin);while(c==' '||c=='\n'||c=='\r'||c=='\t');
		if(c=='-'){
			neg=true;
			c=fgetc(fin);
		}
		for(;c>='0'&&c<='9';c=fgetc(fin))x=(x<<1)+(x<<3)+(c^48);
		if(neg)return -x;
		return x;
	}
	inline void putint(int x){
		neg=x<0;
		if(neg)x=-x;
		i=0;
		do{
			a[i++]=x%10+48;
			x/=10;
		}while(x);
		if(neg)putchar('-');
		for(j=i-1;j>=0;j--)putchar(a[j]);
	}
	inline void fputi(FILE* fout,int x){
		neg=x<0;
		if(neg)x=-x;
		i=0;
		do{
			a[i++]=x%10+48;
			x/=10;
		}while(x);
		if(neg)putchar('-');
		for(j=i-1;j>=0;j--)fputc(a[j],fout);
	}
	inline void fputi(int x,FILE* fout){
		neg=x<0;
		if(neg)x=-x;
		i=0;
		do{
			a[i++]=x%10+48;
			x/=10;
		}while(x);
		if(neg)putchar('-');
		for(j=i-1;j>=0;j--)fputc(a[j],fout);
	}
	inline void put(const char* s){
		x=strlen(s);
		for(i=0;i<x;i++)putchar(s[i]);
	}
	inline void fput(FILE* fout,const char* s){
		x=strlen(s);
		for(i=0;i<x;i++)fputc(s[i],fout);
	}
	inline void fput(const char* s,FILE* fout){
		x=strlen(s);
		for(i=0;i<x;i++)fputc(s[i],fout);
	}
	inline void puts(const char* s){
		x=strlen(s);
		for(i=0;i<x;i++)putchar(s[i]);
		putchar('\n');
	}
	inline void fputs(FILE* fout,const char* s){
		x=strlen(s);
		for(i=0;i<x;i++)fputc(s[i],fout);
		fputc('\n',fout);
	}
	inline void fputs(const char* s,FILE* fout){
		x=strlen(s);
		for(i=0;i<x;i++)fputc(s[i],fout);
		fputc('\n',fout);
	}
}
template<typename T>
struct queue{
private:
	static const int maxn=1010;
	T a[maxn];
	int head,tail;
public:
	queue(){
		memset(a,0,sizeof(a));
		head=tail=0;
	}
	void clear(){
		queue();
	}
	int size(){
		return head>tail?tail-head+maxn:tail-head;
	}
	bool empty(){
		return size()==0;
	}
	void push(const T& n){
		a[tail++]=n;
		if(tail==maxn)tail=0;
	}
	T pop(){
		T n=a[head++];
		if(head==maxn)head=0;
		return n;
	}
	T& front(){
		return a[head];
	}
	T& end(){
		return a[tail-1];
	}
	bool in(const int &n){
		for(int i=0;i<size();i++)if(a[head+i>=maxn?head+n-maxn:head+n]==n)return true;
		return false;
	}
	T& operator[](const int& n){
		if(head+n>=maxn)return a[head+n-maxn];
		return a[head+n];
	}
};
struct edge{
	int to,dis,pre;
	edge():to(0),dis(0),pre(-1){}
}e[maxn<<1];
struct node{
	int lch,rch,apple;
	node():lch(0),rch(0),apple(0){}
}a[maxn];
void insert(int,int,int);
int dfs(int,int);
void bfs();
queue<int>q;
int last[maxn],len=0,f[maxn][maxn];
bool vis[maxn][maxn]={{false}};
int MAIN();
int haha=MAIN();
int main(){;}
int x,y,z,n,m;
inline int MAIN(){
#define COGS
#ifdef COGS
	freopen("ecappletree.in","r",stdin);
	freopen("ecappletree.out","w",stdout);
#endif
	memset(last,-1,sizeof(last));
	n=mine::getint();
	m=mine::getint();
	for(int i=1;i<n;i++){
		x=mine::getint();
		y=mine::getint();
		z=mine::getint();
		insert(x,y,z);
		insert(y,x,z);
	}
	bfs();
	mine::putint(dfs(1,m));
	return 0;
}
void insert(int x,int y,int z){
	e[len].to=y;
	e[len].dis=z;
	e[len].pre=last[x];
	last[x]=len++;
}
int dfs(int i,int j){
	if(!i||!j)return 0;
	if(vis[i][j])return f[i][j];
	vis[i][j]=true;
	//if(!a[i].lch&&!a[i].rch)return f[i][j]=a[i].apple;
	f[i][j]=max(dfs(a[i].lch,j-1)+a[a[i].lch].apple,dfs(a[i].rch,j-1)+a[a[i].rch].apple);
	for(int k=0;k<j-1;k++)f[i][j]=max(f[i][j],dfs(a[i].lch,k)+dfs(a[i].rch,j-k-2)+a[a[i].lch].apple+a[a[i].rch].apple);
	return f[i][j];
}
/*Thanks to Ms. New_Beeؼ ...
int DP(int i,int j){
	if(i==0||j==0)return 0;
	if(f[i][j]!=0)return f[i][j];
	f[i][j]=getmax(f[i][j],DP(a[i].lson,j-1)+apple[i][a[i].lson]);
	f[i][j]=getmax(f[i][j],DP(a[i].rson,j-1)+apple[i][a[i].rson]);
	int t=apple[i][a[i].lson]+apple[i][a[i].rson];
	for(int k=0;k<=j-2;k++){
		f[i][j]=getmax(f[i][j],DP(a[i].lson,k)+DP(a[i].rson,j-2-k)+t);
	}
	return f[i][j];
}*/
bool ok[maxn]={false};
void bfs(){
	int x,y;
	q.push(1);
	while(!q.empty()){
		x=q.pop();
		if(ok[x])continue;
		ok[x]=true;
		for(int i=last[x];i!=-1;i=e[i].pre){
			y=e[i].to;
			if(ok[y])continue;
			a[y].apple=e[i].dis;
			if(a[x].lch)a[x].rch=y;
			else a[x].lch=y;
			q.push(y);
		}
	}
}