学步园

/*
题意：一棵有权树，从根结点中放入K个机器人，求用这K个机器人遍历所有的结点最少的权值和
分析：dp[i][j]表示对于以i结点为根结点的子树，放j个机器人所需要的权值和。
      当j=0时表示放了一个机器人下去，遍历完结点后又回到i结点了。状态转移方程类似背包
  如果最终的状态中以i为根结点的树中有j(j>0)个机器人，那么不可能有别的机器人r到了这棵树后又跑到别的树中去
  因为那样的话，一定会比j中的某一个到达i后跑与r相同的路径再回到i，再接着跑它的路径要差(多了一条i回去的边)
  这样的话，如果最后以i为根结点的树中没有机器人，那么只可能是派一个机器人下去遍历完后再回来
*/
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

const __int64 maxn=11000;
const __int64 maxm=21000;
struct edge
{
	__int64 u,v,w,next;
}e[maxm];
__int64 edgeNum,first[maxn],dp[maxn][15];

void Addedge(__int64 u,__int64 v,__int64 w)
{
	e[edgeNum].u=u,e[edgeNum].v=v,e[edgeNum].w=w,e[edgeNum].next=first[u],first[u]=edgeNum++;
	e[edgeNum].u=v,e[edgeNum].v=u,e[edgeNum].w=w,e[edgeNum].next=first[v],first[v]=edgeNum++;
}

void DFS(__int64 t,__int64 p)
{
	__int64 ii,i,j,k;
	for(k=first[t];k!=-1;k=e[k].next)
	{
		i=e[k].v;
		if(i==p) continue;
		DFS(i,t);
	}
   /* 赋初值0时，可不用管叶子结点了
   //first[t]=-1时说明树中只有一个结点
	if(first[t]==-1||(e[first[t]].next==-1&&p!=-1))//叶子结点,注意一定要把根结点排除。
	{
		for(i=0;i<=10;i++)
			dp[t][i]=0;
		return;
	}*/
	for(k=first[t];k!=-1;k=e[k].next)
	{
		i=e[k].v;
		if(i==p) continue;
		for(j=10;j>=0;j--)//跟01背包类似，方向不能换。
		{//此时的dp[i][j]表示以i为根结点的子树中前面的子树(包括这棵子树)总分配了j个机器人的最少权值和
			/*if(!dp[t][j])//第一棵子树
			{
				if(j) 
				{//最多放j个在该子树中，不一定要全部到该子树中(有一些机器人就停在这个结点上)。当然一个不放肯定不是最好的
					for(ii=1;ii<=j;ii++)
						if(dp[t][j]==0||dp[t][j]>dp[i][ii]+ii*e[k].w)
							dp[t][j]=dp[i][ii]+ii*e[k].w;
				}
				else dp[t][0]=dp[i][0]+2*e[k].w;//放下一个又退回来
				continue;
			}
			else//否则，若该子树放0个机器人*///这一段也可以不要
				dp[t][j]+=dp[i][0]+2*e[k].w;
			for(ii=1;ii<=j;ii++)//该子树放[1,j]个机器人
			{
				if(dp[t][j]>dp[t][j-ii]+dp[i][ii]+ii*e[k].w)
					dp[t][j]=dp[t][j-ii]+dp[i][ii]+ii*e[k].w;
			}
		}
	}
}
int main()
{
	__int64 n,s,k,i,u,v,w;
	while(scanf("%I64d%I64d%I64d",&n,&s,&k)!=EOF)
	{
		memset(first,-1,sizeof(first));
		for(edgeNum=0,i=1;i<n;i++)
		{
			scanf("%I64d%I64d%I64d",&u,&v,&w);
			Addedge(u,v,w);
		}
		memset(dp,0,sizeof(dp));
		DFS(s,-1);
		printf("%I64d\n",dp[s][k]);
	}
	return 0;
}