Universal Cup Judging System

Universal Cup

時間限制: 1 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

有 $n$ 座城市,編號由 1 到 $n$。仲有 $n - 1$ 條雙向道路連接呢啲城市,令到對於任意兩座城市 $x$ 同 $y$,都存在一條由 $x$ 去到 $y$ 嘅路徑。第 $i$ 條道路連接城市 $u_i$ 同 $v_i$,費用係 $c_i$。每次你經過第 $i$ 條道路嗰陣,都要花費 $c_i$ 個金幣。

你而家喺城市 1,想去旅行造訪晒所有城市。每一秒,如果你喺城市 $x$,你可以揀一座透過道路同城市 $x$ 直接相連嘅城市 $y$,移動去城市 $y$,並畀相應道路嘅費用。每條道路最多只可以經過兩次。當你造訪晒所有城市並且返到城市 1 嗰陣,就可以結束你嘅旅行。旅行嘅費用係你所做嘅所有移動嘅總費用。

仲有一個整數 $k$。喺旅行期間,你可以使用一次免費優惠券,令你接下來嘅 $k$ 次移動唔使錢。

對於由 0 到 $2n - 2$ 嘅每個 $k$,你應該計算造訪晒所有城市並最優咁使用優惠券嘅旅行最小費用。

輸入格式

第一行包含一個整數 $t$($1 \le t \le 400$),代表測試資料嘅數量。對於每組測試資料:

第一行包含一個整數 $n$($1 \le n \le 2000$),代表城市嘅數量。

跟住落嚟嘅 $n - 1$ 行描述道路。呢啲行入面嘅第 $i$ 行包含三個整數 $u_i$、$v_i$ 同 $c_i$($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$),代表第 $i$ 條道路連接嘅城市同埋嗰條道路嘅費用。

任意兩座城市之間都存在路徑。$n$ 嘅總和唔超過 $2000$。

輸出格式

對於每組測試資料,輸出一行包含 $2n - 1$ 個整數:對於 $k$ 由 0 到 $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

備註

喺第一組測試資料入面,我哋總係可以沿住路徑 $1, 2, 3, 2, 4, 5, 4, 2, 1$ 旅行,費用序列係 $2, 3, 3, 1, 3, 3, 1, 2$。每個 $k$ 對應嘅免費區間如下所示。

$k$ 免費區間 答案
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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.