记录编号	350265	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	树和机器人	最终得分	100
用户昵称	cwm大佬%%%	是否通过	通过
代码语言	C++	运行时间	0.414 s
提交时间	2016-11-15 17:35:29	内存使用	11.35 MiB

#include<cstdio>
#include<cstring>

const int N=100000,K=20+5,INF=0x7fffffff/10;

struct P{
	int to,v,nex;
};
P tree[N];
int head[N];
int top=0;

int f[N][K];
int n,r,k;

inline int Min(int x,int y){return x<y?x:y;}

void dp(int p,int fa=-1){
	if(p==-1)return;
	for(int l=head[p];l!=-1;l=tree[l].nex)if(tree[l].to!=fa){
		dp(tree[l].to,p);
		for(int i=k;i>=0;i--){
			f[p][i]+=f[tree[l].to][0]+tree[l].v*2;
			for(int j=1;j<=i;j++)
				f[p][i]=Min(f[p][i],f[p][i-j]+f[tree[l].to][j]+tree[l].v*j);
		}
	}
}

void add_edge(int a,int b,int v){
	tree[top]=(P){b,v,head[a]};
	head[a]=top++;
	tree[top]=(P){a,v,head[b]};
	head[b]=top++;
}

int main()
{
	freopen("trobot.in","r",stdin);
	freopen("trobot.out","w",stdout);
	memset(head,-1,sizeof(head));
	memset(tree,-1,sizeof(tree));
	memset(f,0,sizeof(f));
	scanf("%d%d%d",&n,&r,&k);
	for(int i=1;i<n;i++){
		int a,b,v;
		scanf("%d%d%d",&a,&b,&v);
		add_edge(a,b,v);
	}
	dp(r);
	//for(int i=1;i<=n;i++,printf("\n%d:",i))for(int j=0;j<=k;j++)printf("%d ",f[i][j]);
	printf("%d",f[r][k]);
	return 0;
}