Universal Cup Judging System

Universal Cup

Limite de temps : 1 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

有 $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.