记录编号	350117	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	树和机器人	最终得分	100
用户昵称	jmisnal	是否通过	通过
代码语言	C++	运行时间	0.581 s
提交时间	2016-11-15 16:02:03	内存使用	10.54 MiB

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
struct data{
	int to,next,v;
}e[100005];
int head[80005],cnt;
void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;
}
int n,root,k;
ll f[50005][23];
void dp(int now,int fa)
{
//	cout<<now<<endl;
	for(int i=head[now];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa)continue;
		dp(to,now);
		for(int j=k;j>=0;j--)
		{
			f[now][j]  += f[to][0]+(ll)2*e[i].v;
			
			for(int p=1;p<=j;p++)
				f[now][j]=min(f[now][j], f[now][ j-p ] +f[ to ][ p ]+(ll)p*e[i].v  ); 
		}
		
	}
}
int main()
{
	freopen("trobot.in","r",stdin);
	freopen("trobot.out","w",stdout);

	scanf("%d%d%d",&n,&root,&k);
	for(int i=1;i<n;i++)
	{
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		insert(x,y,z);insert(y,x,z);
	}
	dp(root,0);
	printf("%lld",f[root][k]);
	return 0;
}