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

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 5e4 + 10;

struct Edge {
	int to, ne, v;
	Edge() {}
	Edge(int to_, int ne_, int v_) { to = to_, ne = ne_, v = v_; }
} e[maxn << 1];
int head[maxn], ecnt;
inline void add_edge(int fr, int to, int v) {
	e[++ecnt] = Edge(to, head[fr], v), head[fr] = ecnt;
	e[++ecnt] = Edge(fr, head[to], v), head[to] = ecnt;
}

int n, r, k;
long long dp[maxn][25];

inline void read() {
	scanf("%d %d %d", &n, &r, &k);
	int fr, to, v;
	for (int i = 1; i <= n - 1; i++) {
		scanf("%d %d %d", &fr, &to, &v);
		add_edge(fr, to, v);
	}
}

void cal(int now, int fr) {
	for (int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if (to == fr) continue;
		
		cal(to, now);
		for (int now_use = k; now_use >= 0; now_use--) {
			dp[now][now_use] += dp[to][0] + 1ll * 2 * e[i].v;
						
			for (int to_use = 1; to_use <= now_use; to_use++) { 
				dp[now][now_use] = min(dp[now][now_use], dp[now][now_use - to_use] + dp[to][to_use] + 1ll * to_use * e[i].v);
			}
		}
	}
} 

inline void solve() {
	cal(r, -1);
	printf("%lld\n", dp[r][k]);
}

int main() {
	freopen("trobot.in","r",stdin);
	freopen("trobot.out","w",stdout);
	read();
	solve();
	return 0;
}