F1160. 树上的游走序列

时间限制：1000ms 内存限制：256MiB 标签：动态规划, 树形DP

【题目描述】

给定一棵 $n$ 个结点的树，结点编号为 $1$ 到 $n$。树中共有 $n-1$ 条边，第 $i$ 条边连接结点 $u_i$ 与结点 $v_i$，长度为 $w_i$。

记 $\mathrm{dist}(x,y)$ 为结点 $x$ 与结点 $y$ 之间唯一简单路径上所有边的长度之和。

你需要从树中选出 $k$ 个互不相同的结点，并把它们按某种顺序排成一个长度为 $k$ 的序列 $a_1,a_2,\ldots,a_k$。这个序列的代价是相邻两项在树上距离的总和，即 $\sum_{i=1}^{k-1}\mathrm{dist}(a_i,a_{i+1})$。

求所有选法与排列方式中，代价的最小值。

【输入描述】

第一行一个整数 $T$，表示数据的组数。

接下来依次给出 $T$ 组数据，每组数据的格式如下：

• 第一行两个整数 $n,k$，表示结点的个数与需要选出的结点个数；
• 接下来 $n-1$ 行，每行三个整数 $u_i,v_i,w_i$，描述第 $i$ 条边。

对于所有数据，保证：

• $1\le T\le100$；
• $2\le n\le3000$；
• $1\le k\le n$；
• $1\le u_i,v_i\le n$，$u_i\ne v_i$；
• $1\le w_i\le10^5$；
• 给出的 $n-1$ 条边恰好构成一棵树；
• 所有数据的 $n$ 之和不超过 5000。

【输出描述】

每组数据输出一行，一个整数，表示代价的最小值。

【样例 1】

【样例 1 输入】

4
5 3
1 2 2
2 3 3
3 4 6
3 5 1
4 4
1 2 6
2 3 3
3 4 5
3 2
1 2 9
1 3 5
2 1
1 2 7

【样例 1 输出】

4
14
5
0

【样例 1 解释】

第一组数据里，$1$、$2$、$3$、$4$ 依次相连，边长是 $2$、$3$、$6$，$3$ 号结点下面还挂着 $5$ 号结点，边长 $1$。要从五个点里挑三个，选 $2$、$3$、$5$ 最省：从 $5$ 走到 $3$ 用 $1$，从 $3$ 走到 $2$ 又用 $3$，一共 $4$。把 $5$ 换成 $4$，光从 $5$ 走到 $4$ 就要先走 $1$ 再走 $6$，已经超过 $4$ 了；换成 $1$，$5$ 到 $1$ 要 $1+3+2=6$。所以最小代价是 $4$。

第二组数据里 $k=4$ 正好等于 $n$，四个结点全都要走到，只能顺着 $1\to2\to3\to4$ 这条链走一遍，代价是 $6+3+5=14$。

第三组数据只要两个结点，只要路径最短即可，$1$ 与 $3$ 之间的边长为 $5$，比 $1$ 与 $2$ 之间的 $9$ 更短，所以答案是 $5$。

第四组数据 $k=1$，序列里只有一个结点，没有相邻的一对，代价是 $0$。

【样例 2】

【样例 2 输入】

5
6 5
6 1 4
2 1 6
4 3 9
2 3 3
3 5 2
6 3
4 6 2
1 3 6
1 2 3
3 4 2
1 5 5
5 3
4 2 1
4 5 4
3 1 8
2 1 6
6 4
5 3 6
6 2 6
1 3 5
2 1 9
3 4 5
5 3
3 2 5
1 4 8
1 2 4
1 5 9

【样例 2 输出】

15
4
5
19
9

【数据规模与约定】