2548. 树和机器人

问题描述

给定一棵n个节点的树，树根为r，在根节点可以放出机器人，机器人的总数为k，机器人每经过一个道路都会有一定的能量耗费v，返回亦需要同样的耗费，要求机器人将n个节点全部经过至少一遍，机器人可以在任何一个节点返回基地，即机器人不需要返回根节点，求能量耗费的最小值。

输入格式

第一行三个整数n,r,k分别表示节点数，树根编号，提供的机器人个数
接下来n - 1行每行三个整数a,b,v表示连接a,b两个点的边，机器人每经过一次的能量耗费为v

输出格式

一行一个整数表示探索整棵树的最小花费

输入样例

5 1 2
1 2 4
2 3 2
2 4 1
1 5 3 

输出样例

11 

数据范围

对于5%的数据，$n \le 20, k \le 10$

对于另外5%的数据，$n \le 100, k \le 3$

对于另外5%的数据，$v = 1$

对于另外5%的数据，$所有边的v值相等$

对于另外10%的数据，$树形成了一条链$

对于另外10%的数据，$k = 1$

对于另外20%的数据，$n \le 1000, k \le 10$

对于全部的数据，$1 \le n \le 5 * 10^4, 1 \le k \le 20, 0 \le v \le 10^4$