| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 6 초 | 512 MB | 82 | 32 | 20 | 35.088% |
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 ui, vi, wi, describing an edge from ui to vi with weight wi in the tree (1 ≤ ui, vi ≤ n, ui ≠ vi, −109 ≤ wi ≤ 109).
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.
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
Camp > Petrozavodsk Programming Camp > Summer 2019 > Day 2: 300iq Contest 2 J번
Contest > Open Cup > 2019/2020 Season > Stage 1: Grand Prix of Kazan J번