P7600 [APIO2021] Closed Roads

This problem only supports C++ submissions. When submitting, you do not need to include the `roads.h` header file. You only need to paste the content of `roads.h` from the attachment at the beginning of your code.

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.

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]$

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

# 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