记录编号	357161	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2548.树和机器人	最终得分	100
用户昵称	KCkwok	是否通过	通过
代码语言	C++	运行时间	0.471 s
提交时间	2016-12-09 14:05:50	内存使用	11.57 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<cctype>
using namespace std;
typedef long long LL;
const int MAXN=5e4+10;
int N,ROOT,K;
struct EDGE{
	int to,nxt;
	LL val;
}e[MAXN*2];
int head[MAXN];
int ecnt;
LL dp[MAXN][25];
 
inline void addedge(int u,int v,LL w){
	ecnt++;
	e[ecnt].to=v;
	e[ecnt].val=w;
	e[ecnt].nxt=head[u];
	head[u]=ecnt;
}
 
inline LL get_ll(){
	LL res=0,f=1;char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		res=(res<<3)+(res<<1)+ch-'0';
		ch=getchar(); 
	}
	return res*f;
}
 
void DFS(int x,int fa){
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(to==fa)continue;
		DFS(to,x);
		for(int k=K;k>=0;k--){
			dp[x][k]+=dp[to][0]+2*e[i].val;
			for(int j=1;j<=k;j++){
				dp[x][k]=min(dp[x][k],dp[x][k-j]+dp[to][j]+j*e[i].val);
			}
		}
	}
}
 
void read(){
	N=get_ll();ROOT=get_ll();K=get_ll();
	for(int i=1;i<N;i++){
		int u,v,w;
		u=get_ll();v=get_ll();w=get_ll();
		addedge(u,v,w);
		addedge(v,u,w);
	}
}
 
void work(){
	DFS(ROOT,-1);
	cout<<dp[ROOT][K]<<"\n";
}
 
int main(){
	freopen("trobot.in", "r", stdin);
    freopen("trobot.out", "w", stdout); 
	read();
	work();
	return(0);
}