比赛场次	348
比赛名称	20161115
比赛状态	已结束比赛成绩
开始时间	2016-11-15 08:25:00
结束时间	2016-11-15 12:00:00
开放分组	全部用户
注释介绍	完整题目(带背景)和标程题解以及数据生成器，百度网盘，链接: https://pan.baidu.com/s/1jIfmIYM 密码: t2r5

题目名称	树和机器人
输入输出	`trobot.in/out`
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试点数	20 简单对比

用户	结果	时间	内存	得分
Ostmbh	AAAAAAAAAAAAAAAAAAAA	0.262 s	7.37 MiB	100
KZNS	AAAAAAAAAAAAAAAAAAAA	0.305 s	1.02 MiB	100
最长上升子序列	AAAAAAAAAAAAAAAAAAAA	0.316 s	6.42 MiB	100
Fmuckss	AAAAAAAAAAAAAAAAAAAA	1.031 s	11.19 MiB	100
cwm大佬%%%	WWWWAAAAWWWWWWWWWWWW	0.177 s	1.91 MiB	20
jmisnal	AWWWAAWWWWWWWWWWWWWW	0.094 s	12.37 MiB	15
jinqiu	AWWWAAWWWWWWWWWWWWWW	0.106 s	0.31 MiB	15
NVIDIA	AWWWAAWWWWWWWWWWWWWW	0.124 s	0.31 MiB	15
残星誓言	AWWWAAWWWWWWWWWWWWWW	0.126 s	1.25 MiB	15
coolkid	AWWWAAWWWWWWWWWWWWWW	0.128 s	5.65 MiB	15
iortheir	AWWWAAWWWWWWWWWWWWWW	0.170 s	0.30 MiB	15
srO cwm Orz	AWWWAAWWWWWWWWWWWWWW	0.181 s	0.94 MiB	15
Hoohan(%Dalao)	AWWWAAWWWWWWWWWWWWWW	0.400 s	0.31 MiB	15
24193	AWWWAAWWWWWWWWWWWWWW	0.422 s	0.89 MiB	15
祖国栋梁	AWWWAAWWWWWWWWWWWWWW	0.449 s	0.31 MiB	15
Riolu	AWWWTTAAWWWWTTTTTTTT	11.080 s	5.24 MiB	15
123	WWEEEEEEWWWWEEEEEEEE	1.203 s	3.92 MiB	0
BIRD	RRRRRRRRRRRRTTTTTTTT	8.043 s	1.76 MiB	0
Rapiz	WWTTTTTTWWWWTTTTTTTT	15.493 s	11.15 MiB	0

树和机器人

★★☆ 输入文件：trobot.in 输出文件：trobot.out 简单对比
时间限制：1 s 内存限制：256 MiB

问题描述

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

输入格式

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

输出格式

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

输入样例

输出样例

数据范围

对于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$