| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.3 초 | 1024 MB | 139 | 15 | 15 | 12.097% |
Orange the Cat found a tree (an undirected connected acyclic graph) with $N$ vertices numbered from 1ドル$ to $N$. On each edge $i$ (1ドル ≤ i < N$) connecting vertices $x_i$ and $y_i$ there are $c_i$ special cat treats.
Orange can choose exactly $K$ vertices, walk from the root of the tree to each of the chosen vertices along the paths from the root to the respective vertices and take all the cat treats along those paths. Of course, he can only take the treats on each edge once. Because Orange is a curious cat, he wants to know the maximum possible number of treats he could take by choosing the $K$ vertices optimally, if the root of the tree were vertex $i,ドル for each $i$ from 1ドル$ to $N$.
The first line of the input contains two integers $N$ and $K,ドル the number of vertices of the tree and the number of vertices Orange will choose, respectively. The next $N - 1$ lines contain three integers each, $x_i,ドル $y_i$ and $c_i,ドル describing the edges of the tree.
On line $i$ for 1ドル ≤ i ≤ N$ output the maximum number of treats Orange could take if the root of the tree were vertex $i$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 8 | $N ≤ 18$ |
| 2 | 11 | $N ≤ 200,ドル $K ≤ 20$ |
| 3 | 17 | $N ≤ 1,000円,ドル $K ≤ 100$ |
| 4 | 20 | $N ≤ 2,000円$ |
| 5 | 12 | $K = 1$ |
| 6 | 32 | No further restrictions |
11 3 1 2 5 2 3 3 2 6 5 3 4 4 3 5 2 1 7 6 7 8 4 7 9 5 1 10 1 10 11 1
28 28 28 32 30 32 28 32 32 29 30
If the root is vertex 1ドル,ドル then Orange can choose vertices 4ドル,ドル 6ドル$ and 9ドル$. The paths from the root to the chosen vertices are 1ドル − 2 − 3 − 4,ドル 1ドル − 2 − 6,ドル 1ドル − 7 − 9$ and the number of treats along those paths is 5ドル + 3 +たす 4 +たす 5 +たす 6 +たす 5 =わ 28$. Note that the treats on edge 1ドル − 2$ are only counted once.