406260: GYM102331 J 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 \leq (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 \leq n \leq 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 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$, $$$-10^9 \leq w_i \leq 10^9$$$).

It is guaranteed that the given graph is a tree.

Output $$$n - 1$$$ integers: the largest weights of the matchings with $$$1, 2, \ldots, n - 1$$$ edges. If there is no such matching for the current $$$k$$$, print "?" instead.

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

5 6 ? ? 

10
2 8 -5
5 10 5
3 4 -5
1 6 5
3 9 5
1 7 -3
4 8 -5
10 8 -5
1 8 -3

5 10 15 10 ? ? ? ? ? 

2
1 2 35

35 

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.