记录编号	356479	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	树和机器人	最终得分	100
用户昵称	Ostmbh	是否通过	通过
代码语言	C++	运行时间	0.260 s
提交时间	2016-11-30 21:31:31	内存使用	7.37 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=50000+10;
int f[maxn][30]={0};
inline void read(int &x){
	x=0;
	char c=getchar();
	bool flag=0;
	while(c<'0'||c>'9'){
		if(c=='-')
			flag=1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	if(flag)
		x=-x;
}
struct edge{
    int v,t,next;
}E[maxn<<1];
int head[maxn],edge=1;
void addedge(int f,int t,int v){
    E[edge].t=t;E[edge].v=v;E[edge].next=head[f];head[f]=edge++;
    E[edge].t=f;E[edge].v=v;E[edge].next=head[t];head[t]=edge++;
}
int m,n,s;
void dp(int x,int fa){
    for(int i=head[x];i;i=E[i].next){
        int t=E[i].t,v=E[i].v;
        if(t==fa) 
			continue;
        dp(t,x);
        for(int j=m;j>=0;j--){
            f[x][j]+=f[t][0]+v*2;
            for(int k=1;k<=j;k++)
				f[x][j]=min(f[x][j],f[x][j-k]+f[t][k]+v*k);
        }
    }
}
int main(){
    freopen("trobot.in","r",stdin);
    freopen("trobot.out","w",stdout);
    read(n),read(s),read(m);
	int x,y,z;
    for(int i=1;i<=n-1;i++){
        read(x),read(y),read(z);
        addedge(x,y,z);
    }
    dp(s,0);
    printf("%d\n",f[s][m]);
    return 0;
}