Universal Cup Judging System

Universal Cup

时间限制: 1 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

1부터 $n$까지 번호가 매겨진 $n$개의 도시가 있습니다. 또한 이 도시들을 연결하는 $n - 1$개의 양방향 도로가 있어서, 임의의 두 도시 $x$와 $y$에 대해 $x$에서 $y$로 가는 경로가 존재합니다. $i$번째 도로는 도시 $u_i$와 $v_i$를 연결하며 비용 $c_i$를 가집니다. 도로 $i$를 지날 때마다 $c_i$개의 동전을 지불해야 합니다.

당신은 현재 도시 1에 있으며 모든 도시를 방문하는 여행을 하려고 합니다. 매 초마다 도시 $x$에 있다면, 도로로 도시 $x$와 직접 연결된 도시 $y$를 하나 선택하여 도시 $y$로 이동하고 해당 도로의 비용을 지불할 수 있습니다. 각 도로는 최대 두 번까지만 지날 수 있습니다. 모든 도시를 방문하고 다시 도시 1에 도착하면 여행을 마칠 수 있습니다. 여행의 비용은 수행한 모든 이동 비용의 총합입니다.

또한 정수 $k$가 주어집니다. 여행 중 무료 쿠폰을 한 번 사용할 수 있으며, 이를 사용하면 이후 $k$번의 이동에 대해 비용이 들지 않습니다.

0부터 $2n - 2$까지의 모든 $k$에 대해, 모든 도시를 방문하고 쿠폰을 최적으로 사용했을 때의 최소 여행 비용을 구하세요.

입력

첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 $t$ ($1 \le t \le 400$)가 주어집니다. 각 테스트 케이스에 대해:

첫 번째 줄에 도시의 개수를 나타내는 정수 $n$ ($1 \le n \le 2000$)이 주어집니다.

다음 $n - 1$개의 줄에는 도로의 정보가 주어집니다. 이 중 $i$번째 줄에는 $i$번째 도로가 연결하는 두 도시와 그 도로의 비용을 나타내는 세 정수 $u_i$, $v_i$, $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$)가 주어집니다.

임의의 두 도시 사이에는 경로가 존재합니다. 모든 테스트 케이스에서 $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.