Universal Cup Judging System

Universal Cup

実行時間制限: 1 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Það eru $n$ borgir, númeraðar frá 1 til $n$. Einnig eru $n - 1$ tvístefnuvegir sem tengja þessar borgir, þannig að fyrir sérhverjar tvær borgir $x$ og $y$ er til vegur frá $x$ til $y$. $i$-ti vegurinn tengir borgirnar $u_i$ og $v_i$ og hefur kostnaðinn $c_i$. Í hvert sinn sem þú ferð um veg $i$ eyðir þú $c_i$ myntum.

Þú ert núna í borg 1 og vilt ferðast til að heimsækja allar borgirnar. Á hverri sekúndu, ef þú ert í borg $x$, geturðu valið borg $y$ sem er beintengd við borg $x$ með vegi, fært þig yfir í borg $y$ og greitt kostnaðinn fyrir viðkomandi veg. Hvern veg má fara í mesta lagi tvisvar. Þegar þú hefur heimsótt allar borgirnar og ert í borg 1 geturðu lokið ferðalaginu. Kostnaður ferðalagsins er heildarkostnaður allra færzlna sem þú gerðir.

Einnig er gefin heiltala $k$. Á ferðalagi þínu geturðu notað ókeypis afsláttarmiða einu sinni, sem gerir það að verkum að næstu $k$ færslur þínar kosta ekkert.

Fyrir hvert $k$ frá 0 til $2n - 2$ áttu að reikna lágmarkskostnað ferðalags sem heimsækir allar borgirnar og notar afsláttarmiðann á sem bestan hátt.

Inntak

Fyrsta línan inniheldur eina heiltölu $t$ ($1 \le t \le 400$), fjölda prófunartilvika. Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 2000$), sem táknar fjölda borga.

Næstu $n - 1$ línur lýsa vegunum. $i$-ta línan af þessum línum inniheldur þrjár heiltölur, $u_i$, $v_i$ og $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), sem tákna borgirnar sem $i$-ti vegurinn tengir og kostnað þess vegar.

Það er vegur á milli sérhvers pars af borgum. Summa $n$ fer ekki yfir $2000$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur $2n - 1$ heiltölur: svörin fyrir $k$ frá 0 til $2n - 2$.

Dæmi

Inntak

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

Úttak

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

Athugasemd

Í fyrsta prófunartilvikinu getum við alltaf ferðast eftir leiðinni $1, 2, 3, 2, 4, 5, 4, 2, 1$, með kostnaðarrununni $2, 3, 3, 1, 3, 3, 1, 2$. Kostnaðarlausu bútar fyrir hvert $k$ eru sýndir hér að neðan.

$k$ kostnaðarlaus bútur svar
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.