Jiry Matchings

Time limit6sMemory limit512 MB

Summary

Given a weighted tree, find the maximum total weight of a matching with k edges for each k from 1 to n-1, or print ? if none exists.

Level: Hard8 of 10
Topics: Tree, Dynamic programming, Heap
Solved: No attempts yet

Problem

Ruyi Ji has a tree with $n$ vertices, numbered from $1$ to $n$ . Each edge has a weight.

For each $k \le n - 1$ , find the largest total weight of a matching with $k$ edges. If no matching with $k$ edges exists, print "?" instead.

Input

The first line contains one integer $n$ ( $2 \le n \le 200000$ ), the number of vertices.

Each of the next $n - 1$ lines contains three integers $u_i$ , $v_i$ , $w_i$ ( $1 \le u_i, v_i \le n$ , $u_i \ne v_i$ , $-10^9 \le w_i \le 10^9$ ), describing an edge between $u_i$ and $v_i$ with weight $w_i$ . The given graph is guaranteed to be a tree.

Output

Print $n - 1$ integers: the largest total weight of a matching with $1, 2, \ldots, n - 1$ edges. Print "?" for each $k$ that has no such matching.

Hint

In the first sample, with $k = 1$ , take the edge $(2, 3)$ with weight $5$ . With $k = 2$ , take the two edges $(2, 4)$ and $(3, 5)$ , for a total weight of $6$ . No matching has more edges than that.

Examples3

Example 1
Input
```
5
1 2 3
2 3 5
2 4 4
3 5 2
```
Expected output
```
5 6 ? ?
```

Example 2

Input

Expected output

5 10 15 10 ? ? ? ? ?

Example 3
Input
```
2
1 2 35
```
Expected output
```
35
```