Universal Cup Judging System

Universal Cup

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

On $n$ kaupunkia, jotka on numeroitu 1:stä $n$:ään. Lisäksi on $n - 1$ kaksisuuntaista tietä, jotka yhdistävät nämä kaupungit siten, että jokaiselle kaupunkiparille $x$ ja $y$ on olemassa polku kaupungista $x$ kaupunkiin $y$. $i$:s tie yhdistää kaupungit $u_i$ ja $v_i$, ja sen hinta on $c_i$. Joka kerta, kun kuljet tien $i$ kautta, käytät $c_i$ kolikkoa.

Olet nyt kaupungissa 1 ja haluat matkustaa vieraillaksesi kaikissa kaupungeissa. Joka sekunti, jos olet kaupungissa $x$, voit valita kaupungin $y$, joka on suoraan yhteydessä kaupunkiin $x$ tiellä, siirtyä kaupunkiin $y$ ja maksaa kyseisen tien hinnan. Jokaisen tien kautta voi kulkea korkeintaan kaksi kertaa. Kun olet vieraillut kaikissa kaupungeissa ja olet kaupungissa 1, voit lopettaa matkasi. Matkan hinta on kaikkien tekemiesi siirtymien yhteenlaskettu hinta.

Annettuna on myös kokonaisluku $k$. Matkasi aikana voit käyttää kerran ilmaiskupongin, jolloin seuraavat $k$ siirtymääsi ovat ilmaisia.

Sinun tulee laskea jokaiselle $k$ väliltä 0 – $2n - 2$ pienin mahdollinen hinta matkalle, joka vierailee kaikissa kaupungeissa ja käyttää kupongin optimaalisesti.

Syöte

Ensimmäinen rivi sisältää yhden kokonaisluvun $t$ ($1 \le t \le 400$), testitapausten lukumäärän. Jokaiselle testitapaukselle:

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 2000$), joka ilmaisee kaupunkien määrän.

Seuraavat $n - 1$ riviä kuvaavat tiet. Näistä riveistä $i$:s sisältää kolme kokonaislukua, $u_i$, $v_i$ ja $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), jotka ilmaisevat $i$:nnen tien yhdistämät kaupungit sekä kyseisen tien hinnan.

Minkä tahansa kaupunkiparin välillä on polku. Lukujen $n$ summa ei ylitä arvoa $2000$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää $2n - 1$ kokonaislukua: vastaukset luvulle $k$ välillä 0 – $2n - 2$.

Esimerkki

Syöte

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

Tuloste

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

Huomautus

Ensimmäisessä testitapauksessa voimme aina kulkea polkua $1, 2, 3, 2, 4, 5, 4, 2, 1$, jonka hintajono on $2, 3, 3, 1, 3, 3, 1, 2$. Ilmaiset osuudet kullekin $k$ on esitetty alla.

$k$ ilmainen osuus vastaus
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.