18477번 - Jiry Matchings 다국어

Ruyi Ji has a tree where the vertices are numbered by integers from 1 to n and each edge has a weight.

For each k ≤ (n − 1), he asked you to find the largest total weight of a matching with k edges if it exists.

The first line of input contains one integer n: the number of vertices in the tree (2 ≤ n ≤ 200 000).

Each of the next n−1 lines contains three integers u_i, v_i, w_i, describing an edge from u_i to v_i with weight w_i in the tree (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, −10⁹ ≤ w_i ≤ 10⁹).

It is guaranteed that the given graph is a tree.

Output n − 1 integers: the largest weights of the matchings with 1, 2, . . . , n − 1 edges. If there is no such matching for the current k, print “?” instead.

In the first sample, with k = 1 you should take edge (2, 3) with weight 5. And with k = 2 you should take two edges, (2, 4) and (3, 5), with total weight 6. There are no matchings with a greater number of edges