Universal Cup Judging System

Universal Cup

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

Terdapat $n$ kota, yang dinomori dari 1 hingga $n$. Terdapat pula $n - 1$ jalan dua arah yang menghubungkan kota-kota ini, sehingga untuk setiap dua kota $x$ dan $y$, terdapat sebuah jalur dari $x$ ke $y$. Jalan ke-$i$ menghubungkan kota $u_i$ dan $v_i$, serta memiliki biaya $c_i$. Setiap kali Anda melewati jalan $i$, Anda menghabiskan $c_i$ koin.

Saat ini Anda berada di kota 1 dan ingin melakukan perjalanan untuk mengunjungi semua kota. Setiap detik, jika Anda berada di kota $x$, Anda dapat memilih sebuah kota $y$ yang terhubung langsung dengan kota $x$ melalui sebuah jalan, berpindah ke kota $y$, dan membayar biaya jalan yang bersangkutan. Setiap jalan dapat dilewati paling banyak dua kali. Ketika Anda telah mengunjungi semua kota dan berada di kota 1, Anda dapat mengakhiri perjalanan Anda. Biaya perjalanan adalah total biaya dari semua perpindahan yang Anda lakukan.

Terdapat pula sebuah bilangan bulat $k$. Selama perjalanan, Anda dapat menggunakan kupon gratis satu kali, yang membuat $k$ perpindahan Anda berikutnya tidak dikenakan biaya.

Untuk setiap $k$ dari 0 hingga $2n - 2$, Anda harus menghitung biaya minimum dari perjalanan yang mengunjungi semua kota dan menggunakan kupon secara optimal.

Masukan

Baris pertama berisi sebuah bilangan bulat $t$ ($1 \le t \le 400$), yaitu banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 2000$), yang menyatakan banyaknya kota.

$n - 1$ baris berikutnya menjelaskan jalan-jalan tersebut. Baris ke-$i$ dari baris-baris ini berisi tiga bilangan bulat, $u_i$, $v_i$, dan $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), yang menyatakan kota-kota yang dihubungkan oleh jalan ke-$i$ dan biaya jalan tersebut.

Terdapat jalur di antara setiap pasang kota. Jumlah dari $n$ tidak melebihi $2000$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi $2n - 1$ bilangan bulat: jawaban untuk $k$ dari 0 hingga $2n - 2$.

Contoh

Masukan

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

Keluaran

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

Catatan

Pada kasus uji pertama, kita selalu dapat melakukan perjalanan sepanjang jalur $1, 2, 3, 2, 4, 5, 4, 2, 1$, dengan barisan biaya $2, 3, 3, 1, 3, 3, 1, 2$. Segmen bebas biaya untuk setiap $k$ ditunjukkan di bawah ini.

$k$ segmen bebas biaya jawaban
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.