1253: 算法提高 金属采集

人类在火星上发现了一种新的金属！这些金属分布在一些奇怪的地方，不妨叫它节点好了。
一些节点之间有道路相连，所有的节点和道路形成了一棵树。一共有 n 个节点，这些节点被编号为 1~n 。
人类将 k 个机器人送上了火星，目的是采集这些金属。
这些机器人都被送到了一个指定的着落点， S 号节点。
每个机器人在着落之后，必须沿着道路行走。当机器人到达一个节点时，它会采集这个节点蕴藏的所有金属矿。
当机器人完成自己的任务之后，可以从任意一个节点返回地球。当然，回到地球的机器人就无法再到火星去了。
我们已经提前测量出了每条道路的信息，包括它的两个端点 x 和 y，以及通过这条道路需要花费的能量 w 。
我们想花费尽量少的能量采集所有节点的金属，这个任务就交给你了。

输入描述:
第一行包含三个整数 n, S 和 k ，分别代表节点个数、着落点编号，和机器人个数。
接下来一共 n-1 行，每行描述一条道路。一行含有三个整数 x, y 和 w ，代表在 x 号节点和 y 号节点之间有一条道路，通过需要花费 w 个单位的能量。所有道路都可以双向通行。

输入样例:

样例1：
5 1 2
1 2 4
2 3 2
2 4 1
1 5 3

样例2：
6 1 3
1 2 1
2 3 1
2 4 1000
2 5 1000
1 6 1000

输出描述:
输出一个整数，代表采集所有节点的金属所需要的最少能量。
输出样例:

样例1：
11

样例2：
3004

样例2解释：
所有机器人在 1 号节点着陆。
第一个机器人的行走路径为 1->6 ， 在 6 号节点返回地球， 花费能量为 1000。
第二个机器人的行走路径为 1->2->3->2->4 ， 在 4 号节点返回地球， 花费能量为 1003。
第一个机器人的行走路径为 1->2->5 ， 在 5 号节点返回地球， 花费能量为 1001。

数据范围：
对于5%的数据，n≤20,k≤10
对于另外5%的数据，n≤100,k≤3
对于另外5%的数据，v=1
对于另外5%的数据，所有边的v值相等
对于另外10%的数据，树形成了一条链
对于另外10%的数据，k=1
对于另外20%的数据，n≤1000,k≤10
对于全部的数据，1≤n≤5∗10^4,1≤k≤20,0≤v≤10^4