Universal Cup Judging System

Universal Cup

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

Det finns $n$ städer, numrerade från 1 till $n$. Det finns också $n - 1$ dubbelriktade vägar som förbinder dessa städer, så att det för varje par av städer $x$ och $y$ finns en väg från $x$ till $y$. Den $i$-te vägen förbinder städerna $u_i$ och $v_i$, och har en kostnad $c_i$. Varje gång du passerar genom väg $i$ spenderar du $c_i$ mynt.

Du befinner dig nu i stad 1 och vill resa för att besöka alla städer. Varje sekund, om du befinner dig i stad $x$, kan du välja en stad $y$ som är direkt förbunden med stad $x$ via en väg, flytta till stad $y$ och betala kostnaden för respektive väg. Varje väg kan passeras högst två gånger. När du har besökt alla städer och befinner dig i stad 1 kan du avsluta din resa. Kostnaden för resan är den totala kostnaden för alla förflyttningar du gjort.

Det finns också ett heltal $k$. Under din resa kan du använda en gratiskupong en gång, vilket gör att dina följande $k$ förflyttningar inte kostar någonting.

För varje $k$ från 0 till $2n - 2$ ska du beräkna den minimala kostnaden för en resa som besöker alla städer och använder kupongen optimalt.

Indata

Den första raden innehåller ett enda heltal $t$ ($1 \le t \le 400$), antalet testfall. För varje testfall:

Den första raden innehåller ett heltal $n$ ($1 \le n \le 2000$), som anger antalet städer.

De följande $n - 1$ raderna beskriver vägarna. Den $i$-te av dessa rader innehåller tre heltal, $u_i$, $v_i$ och $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), som anger städerna som förbinds av den $i$-te vägen samt kostnaden för den vägen.

Det finns en väg mellan varje par av städer. Summan av $n$ överstiger inte $2000$.

Utdata

För varje testfall, skriv ut en rad som innehåller $2n - 1$ heltal: svaren för $k$ från 0 till $2n - 2$.

Exempel

Indata

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

Utdata

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

Anmärkning

I det första testfallet kan vi alltid resa längs vägen $1, 2, 3, 2, 4, 5, 4, 2, 1$, med kostnadsföljden $2, 3, 3, 1, 3, 3, 1, 2$. De kostnadsfria segmenten för varje $k$ visas nedan.

$k$ kostnadsfritt segment 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.