Description

In Si Shui City, there are $N$ intersections (numbered from $0$ to $N-1$). These intersections are connected by $N-1$ two-way roads (numbered from $0$ to $N-2$), so that between any pair of intersections there is a unique path using these roads. Road $i$ ($0 \le i \le N-2$) connects intersections $U[i]$ and $V[i]$.

To raise awareness about environmental protection, the mayor of Si Shui City, Pak Dengklek, plans to hold a Car-Free Day. To promote this event, Pak Dengklek will organize road closures. Pak Dengklek will first choose a non-negative integer $k$, and then close some roads so that each intersection is directly connected to at most $k$ roads that remain open. The cost to close road $i$ is $W[i]$.

Please help Pak Dengklek compute, for every possible non-negative integer $k$ ($0 \le k \le N-1$), the minimum total cost to close roads.

You need to implement the following function:

int64[] minimum_closure_costs(int N, int[] U, int[] V, int[] W)

• $N$: the number of intersections in Si Shui City.

• $U$ and $V$: arrays of size $N-1$, where intersection $U[i]$ and intersection $V[i]$ are directly connected by road $i$.

• $W$: an array of size $N-1$, where the cost to close road $i$ is $W[i]$.

• The function must return an array of size $N$. For each $k$ ($0 \le k \le N-1$), element $k$ is the minimum total cost such that each intersection is directly connected to at most $k$ open roads.

This function will be called exactly once.

Input Format

The sample grader reads the input data in the following format:

• Line $1$: $N$
• Line $2+i$ ($0 \le i \le N-2$): $U[i]$ $V[i]$ $W[i]$

Output Format

The sample grader outputs only one line containing an array, representing the return value of minimum_closure_costs.

5
0 1 1
0 2 4
0 3 3
2 4 2

10 5 1 0 0

4
0 1 5
2 0 10
0 3 5

20 10 5 0

Hint

Examples

Example $1$

Consider the following call:

minimum_closure_costs(5, [0, 0, 0, 2], [1, 2, 3, 4], [1, 4, 3, 2])

In this example, there are $5$ intersections and $4$ roads, connecting intersections $(0,1),(0,2),(0,3)$, and $(2,4)$. The costs to close them are $1,4,3$, and $2$, respectively.

To achieve the minimum total cost:

• If Pak Dengklek chooses $k=0$, then all roads must be closed, and the total cost is $1+4+3+2=10$.
• If Pak Dengklek chooses $k=1$, then roads $0$ and $1$ must be closed, and the total cost is $1+4=5$.
• If Pak Dengklek chooses $k=2$, then road $0$ must be closed, and the total cost is $1$.
• If Pak Dengklek chooses $k=3$ or $k=4$, then no roads need to be closed.

Therefore, minimum_closure_costs should return the array $[10,5,1,0,0]$.

Example $2$

Consider the following call:

minimum_closure_costs(4, [0, 2, 0], [1, 0, 3], [5, 10, 5])

In this example, there are $4$ intersections and $3$ roads, connecting intersections $(0,1),(2,0)$, and $(0,3)$. The costs to close them are $5,10$, and $5$, respectively.

To achieve the minimum total cost:

• If Pak Dengklek chooses $k=0$, then all roads must be closed, and the total cost is $5+10+5=20$.
• If Pak Dengklek chooses $k=1$, then roads $0$ and $2$ must be closed, and the total cost is $5+5=10$.
• If Pak Dengklek chooses $k=2$, then either road $0$ or road $2$ must be closed, and the total cost is $5$.
• If Pak Dengklek chooses $k=3$, then no roads need to be closed.

Therefore, minimum_closure_costs should return the array $[20,10,5,0]$.

Constraints

• $2 \le N \le 10^5$
• $0 \le U[i],V[i] \le N-1$ $(0 \le i \le N-2)$
• Any pair of intersections can reach each other via the roads.
• $1 \le W[i] \le 10^9$ $(0 \le i \le N-2)$.

Hint

Translated by ChatGPT 5