【题意】：给出一棵树，每条边上有一个权值，表示通过这条边的代价。现在有k个机器人在节点s，问用k个机器人访问完整棵树的节点的最少代价是多少。
【题解】：又是树dp+背包的题目。
设状态dp[u][k]表示以u为根节点的子树排了k个机器人下去访问完该子树的节点的最小代价。
如果k == 0，表示排了一个机器人下去访问完之后机器人又返回到节点u。
注意k == 0的时候必定是只有一个机器人下去然后返回，不会有多于一个机器人下去，因为这样肯定不是最优。
然后就是一个01背包 +分组背包，枚举容量时要逆序，因为用了滚动数组。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define pii pair<int, int>
19 #define mp make_pair
20 #define maxn 10050
21 #define maxm 1000050
22
23 int n, s, cnt;
24 int eh[maxn], tot;
25 int dp[maxn][15];
26 struct Edge {
27 int u, v, w, next;
28 }et[maxm];
29
30 void addedge(int u, int v, int w) {
31 Edge e = {u, v, w, eh[u]};
32 et[tot] = e;
33 eh[u] = tot++;
34 }
35
36 void init() {
37 tot = 0;
38 memset(eh, -1, sizeof(eh));
39 }
40
41 void dfs(int u, int fa) {
42 for(int i = eh[u]; i != -1; i = et[i].next) {
43 int v = et[i].v, w = et[i].w;
44 if(v == fa) continue;
45 dfs(v, u);
46 for(int j = cnt; j >= 0; j--) {
47 dp[u][j] += dp[v][0] + 2 * w;
48 for(int k = 1; k <= j; k++) {
49 dp[u][j] = min(dp[u][j], dp[u][j-k] + dp[v][k] + k * w);
50 }
51 }
52 }
53 }
54
55 int main() {
56 int u, v, w;
57 while(~scanf("%d%d%d", &n, &s, &cnt)) {
58 init();
59 memset(dp, 0, sizeof(dp));
60 for(int i = 0; i < n - 1; i++) {
61 scanf("%d%d%d", &u, &v, &w);
62 addedge(u, v, w), addedge(v, u, w);
63 }
64 dfs(s, -1);
65 printf("%d\n", dp[s][cnt]);
66 }
67 return 0;
68 }
69