Universal Cup Judging System

Universal Cup

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

Є $n$ міст, пронумерованих від 1 до $n$. Також є $n - 1$ двосторонніх доріг, що з'єднують ці міста так, що для будь-яких двох міст $x$ і $y$ існує шлях із $x$ до $y$. $i$-та дорога з'єднує міста $u_i$ та $v_i$ і має вартість $c_i$. Щоразу, проходячи дорогою $i$, ви витрачаєте $c_i$ монет.

Зараз ви перебуваєте в місті 1 і хочете здійснити подорож, щоб відвідати всі міста. Щосекунди, перебуваючи в місті $x$, ви можете вибрати місто $y$, яке напряму з'єднане з містом $x$ дорогою, переміститися в місто $y$ і заплатити вартість відповідної дороги. Кожною дорогою можна пройти щонайбільше два рази. Коли ви відвідали всі міста і перебуваєте в місті 1, ви можете завершити подорож. Вартість подорожі дорівнює сумарній вартості всіх здійснених вами переміщень.

Також задано ціле число $k$. Під час подорожі ви можете один раз використати безкоштовний купон, завдяки чому наступні $k$ ваших переміщень не матимуть вартості.

Для кожного $k$ від 0 до $2n - 2$ вам потрібно обчислити мінімальну вартість подорожі, яка відвідує всі міста та оптимально використовує купон.

Вхідні дані

Перший рядок містить одне ціле число $t$ ($1 \le t \le 400$) — кількість тестових випадків. Для кожного тестового випадку:

Перший рядок містить ціле число $n$ ($1 \le n \le 2000$), що позначає кількість міст.

Наступні $n - 1$ рядків описують дороги. $i$-й із цих рядків містить три цілі числа $u_i$, $v_i$ та $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), що позначають міста, з'єднані $i$-ю дорогою, та вартість цієї дороги.

Між будь-якою парою міст існує шлях. Сума $n$ не перевищує $2000$.

Вихідні дані

Для кожного тестового випадку виведіть один рядок, що містить $2n - 1$ цілих чисел: відповіді для $k$ від 0 до $2n - 2$.

Приклад

Вхідні дані

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

Вихідні дані

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

Примітка

У першому тестовому випадку ми завжди можемо подорожувати шляхом $1, 2, 3, 2, 4, 5, 4, 2, 1$ із послідовністю вартостей $2, 3, 3, 1, 3, 3, 1, 2$. Безкоштовні відрізки для кожного $k$ показано нижче.

$k$ безкоштовний відрізок відповідь
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.