P11038 [MX-X3-T5] "RiOI-4" Countless J-Light Decomposition

Original problem link: . --- "If, if, if it really could be like that, that would be nice." Thinking back on each choice she made, Lingluo sometimes wonders whether she once had a better chance. But since everything has already turned out this way, there is no other path except moving forward. No matter what the result is, accept it, learn the lesson, and then... strive for a better future. So, what should be done now is probably to avoid, as much as possible, the worst outcome that might come later. "Avoid risks. Keep your feet on the ground. Make the choice that is most likely to work." "It must be.".

You are given a rooted **weighted** tree with nodes numbered $1 \sim n$. The root is node $1$, and all edge weights are positive integers. A **decomposition** of this tree is defined as follows: for each node, choose some of its children (you may choose all or none) as **heavy children**. The edge between a heavy child and its parent is called a **heavy edge**. Edges that are not heavy edges are called **light edges**. A decomposition is **$\textbf{\textit{i--}}$heavy** if and only if, for every node, the number of its heavy children is at most $i$. A decomposition is **$\textbf{\textit{j--}}$light** if and only if, for every simple path starting from the root (node $1$), the sum of the weights of the light edges on that path is at most $j$. For $i = 0, 1, \cdots, n - 1$, find the minimum $j$ such that there exists an $\textit{i--}$heavy decomposition that is $\textit{j--}$light.

The first line contains a positive integer $n$, representing the size of the tree. The next $n - 1$ lines each contain three positive integers $u_i, v_i, w_i$, indicating that there is an edge of weight $w_i$ between nodes $u_i$ and $v_i$.

Output one line containing $n$ integers, representing the answers for $i = 0, 1, 2, \cdots, n - 1$.

**[Sample Explanation #1]** For Sample 1, the tree is shown below:  When $i = 0$, there is only one possible decomposition: there are no heavy children or heavy edges. The simple path starting from the root with the maximum sum of light-edge weights is $1\textit{---}2\textit{---}4$, and the sum of edge weights is $2$. When $i = 1$, you can use the decomposition shown in the figure, where the bold nodes (except the root) are heavy children. The simple path starting from the root with the maximum sum of light-edge weights is $1\textit{---}2\textit{---}5$, and the sum of light-edge weights is $1$. When $i \ge 2$, you can make all non-root nodes heavy children. Then any simple path starting from the root that passes through the most light edges can only pass through $0$ light edges, so the maximum sum of light-edge weights is $0$. **[Sample Explanation #2]** When $i \ge 3$, you can make all non-root nodes heavy children. Then any simple path starting from the root that passes through the most light edges can only pass through $0$ light edges, so the maximum sum of light-edge weights is $0$. When $i = 0, 1, 2$, I have a very concise explanation, but this space is too small to write it down. **[Constraints]** **This problem uses bundled testdata.** |Subtask|Points|$n \le$|Special properties| |:-:|:-:|:-:|:-:| |$1$|$10$|$10^3$|| |$2$|$18$|$4\times10^4$|| |$3$|$16$|$10^5$|$w_i\le100$| |$4$|$21$|$10^5$|$w_i\le10^5$| |$5$|$35$|$2\times10^5$|| For $100\%$ of the testdata, $1 \le n \le 2\times10^5$, $1 \le w_i \le 10^9$, and the input is guaranteed to be a tree. Translated by ChatGPT 5