#P18715. Travelling

    ID: 18051 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-树上背包子树合并剪除无效容量

Travelling

Travelling

有 nn 座城市,编号 1,2,…,n1,2,\ldots,n,以及连接它们的 n−1n-1 条双向道路。任意两座城市之间都存在路径。第 ii 条道路连接 ui,viu_i,v_i,每经过一次花费 cic_i 枚硬币。

你从城市 11 出发,要访问所有城市,最后回到城市 11。每秒可以沿一条道路从当前城市移动到相邻城市,并支付这条道路的费用。每条道路至多经过两次。 当你已经访问所有城市且回到城市 11 时,可以结束旅行。总费用是所有移动费用之和。

给定一个整数 kk。旅行中可以使用一张免费券一次,使得接下来的连续 kk 次移动不需要付费。

对每个 k=0,1,…,2n−2k=0,1,\ldots,2n-2,分别求访问所有城市、回到城市 11,且最优使用免费券时的最小总费用。不同 kk 可以选择不同的旅行路线。

输入格式

第一行一个整数 tt(1≤t≤4001\le t\le400),表示测试用例数。每个测试用例如下:

第一行一个整数 nn(1≤n≤20001\le n\le2000)。随后 n−1n-1 行,第 ii 行三个整数 ui,vi,ciu_i,v_i,c_i(1≤ui,vi≤n1\le u_i,v_i\le n,0≤ci≤1090\le c_i\le10^9),描述第 ii 条双向道路。

保证任意两点之间有路径。所有测试用例的 nn 之和不超过 20002000。道路费用允许为 00。

输出格式

每个测试用例输出一行 2n−12n-1 个整数,按顺序给出 k=0,1,…,2n−2k=0,1,\ldots,2n-2 的答案。

原样例

2
5
1 2 2
2 3 3
2 4 1
4 5 3
7
1 2 1
1 3 1
1 4 4
3 5 5
3 6 1
6 7 4
18 15 12 10 8 5 3 2 0
32 27 22 21 17 13 12 8 4 3 2 1 0

原样例说明

第一个测试用例中,下面同一条路线对所有 kk 都可以达到最优:

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

对应的费用序列是 2,3,3,1,3,3,1,22,3,3,1,3,3,1,2。各 kk 可选的免费片段如下(与原表一致):

kk 免费费用片段 答案
0 [ ][\ ] 18
1 [3][3] 15
2 [3,3][3,3] 12
3 [2,3,3][2,3,3] 10
4 [3,3,1,3][3,3,1,3] 8
5 [3,3,1,3,3][3,3,1,3,3] 5
6 [2,3,3,1,3,3][2,3,3,1,3,3] 3
7 [2,3,3,1,3,3,1][2,3,3,1,3,3,1] 2
8 [2,3,3,1,3,3,1,2][2,3,3,1,3,3,1,2] 0
kk 免费片段 答案
0 [] 18
1 [3] 15
2 [3, 3] 12
3 [2, 3, 3] 10
4 [3, 3, 1, 3] 8
5 [3, 3, 1, 3, 3] 5
6 [2, 3, 3, 1, 3, 3] 3
7 [2, 3, 3, 1, 3, 3, 1] 2
8 [2, 3, 3, 1, 3, 3, 1, 2] 0