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

Istnieje $n$ miast, ponumerowanych od 1 do $n$. Istnieje również $n - 1$ dwukierunkowych dróg łączących te miasta, tak że dla każdych dwóch miast $x$ i $y$ istnieje ścieżka z $x$ do $y$. $i$-ta droga łączy miasta $u_i$ oraz $v_i$ i ma koszt $c_i$. Za każdym razem, gdy przechodzisz przez drogę $i$, wydajesz $c_i$ monet.

Jesteś teraz w mieście 1 i chcesz odbyć podróż, aby odwiedzić wszystkie miasta. W każdej sekundzie, jeśli znajdujesz się w mieście $x$, możesz wybrać miasto $y$ połączone bezpośrednio z miastem $x$ drogą, przemieścić się do miasta $y$ i zapłacić koszt odpowiedniej drogi. Każda droga może zostać przebyta co najwyżej dwa razy. Gdy odwiedzisz już wszystkie miasta i będziesz w mieście 1, możesz zakończyć swoją podróż. Kosztem podróży jest łączny koszt wszystkich wykonanych ruchów.

Dana jest również liczba całkowita $k$. Podczas podróży możesz raz użyć darmowego kuponu, dzięki czemu kolejne $k$ ruchów nic nie kosztuje.

Dla każdego $k$ od 0 do $2n - 2$ należy obliczyć minimalny koszt podróży, która odwiedza wszystkie miasta i optymalnie wykorzystuje kupon.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 400$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 2000$), oznaczającą liczbę miast.

Kolejne $n - 1$ wierszy opisuje drogi. $i$-ty z tych wierszy zawiera trzy liczby całkowite $u_i$, $v_i$ oraz $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), oznaczające miasta połączone $i$-tą drogą oraz koszt tej drogi.

Pomiędzy każdą parą miast istnieje ścieżka. Suma wartości $n$ nie przekracza $2000$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający $2n - 1$ liczb całkowitych: odpowiedzi dla $k$ od 0 do $2n - 2$.

Przykład

Wejście

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

Wyjście

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

Uwaga

W pierwszym przypadku testowym zawsze możemy podróżować wzdłuż ścieżki $1, 2, 3, 2, 4, 5, 4, 2, 1$ o ciągu kosztów $2, 3, 3, 1, 3, 3, 1, 2$. Darmowe fragmenty dla każdego $k$ pokazano poniżej.

$k$ darmowy fragment odpowiedź
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.