Universal Cup Judging System

Universal Cup

Süre Sınırı: 1 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

1 から $n$ までの番号がついた $n$ 個の都市があります。また、これらの都市を結ぶ $n - 1$ 本の双方向道路があり、任意の 2 つの都市 $x$ と $y$ について $x$ から $y$ への単純道が存在します。$i$ 番目の道路は都市 $u_i$ と $v_i$ を結び、コスト $c_i$ を持ちます。道路 $i$ を通るたびに $c_i$ 枚のコインを消費します。

あなたは現在都市 1 にいて、すべての都市を訪れる旅行をしたいと考えています。毎秒、都市 $x$ にいるとき、道路で都市 $x$ と直接結ばれている都市 $y$ を 1 つ選び、都市 $y$ に移動して対応する道路のコストを支払うことができます。各道路は高々 2 回しか通ることができません。すべての都市を訪れ、かつ都市 1 に戻ってきたとき、旅行を終えることができます。旅行のコストは行ったすべての移動のコストの合計です。

また、整数 $k$ があります。旅行中に 1 回だけ無料クーポンを使うことができ、その後の $k$ 回の移動のコストを 0 にすることができます。

0 から $2n - 2$ までのすべての $k$ について、すべての都市を訪れ、クーポンを最適に使ったときの旅行の最小コストを求めてください。

入力

1 行目には、テストケースの個数を表す 1 つの整数 $t$ ($1 \le t \le 400$) が与えられます。各テストケースについて:

1 行目には、都市の個数を表す整数 $n$ ($1 \le n \le 2000$) が与えられます。

続く $n - 1$ 行は道路を記述します。これらのうち $i$ 行目には、$i$ 番目の道路が結ぶ都市とその道路のコストを表す 3 つの整数 $u_i$, $v_i$, $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$) が与えられます。

任意の 2 都市間には経路が存在します。$n$ の総和は $2000$ を超えません。

出力

各テストケースについて、0 から $2n - 2$ までの $k$ に対する答えである $2n - 1$ 個の整数を 1 行に出力してください。

入出力例

入力

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.