408074: GYM102979 B Best Meeting Places
Description
A tree with $$$N$$$ vertices is given. Vertices are numbered sequentially from $$$1$$$ to $$$N$$$. The $$$i$$$-th edge connects vertices $$$A_i$$$ and $$$B_i$$$, and has weight $$$C_i$$$, for $$$1 \leq i \leq N - 1$$$.
The teleport distance between two vertices of the tree is the maximum weight of the edge on the shortest path connecting them. The teleport distance between a vertex and itself is defined as $$$0$$$.
People living on the tree want to hold $$$N$$$ meetings. The $$$i$$$-th meeting is attended by people living in the vertices numbered from $$$1$$$ to $$$i$$$. This year, because of the spread of coronavirus, the meeting participants will arrive at $$$X$$$ selected locations, and then connect via Internet from these locations.
More formally, for each meeting, we will choose $$$X$$$ pairwise distinct vertices $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_X$$$. Once the vertices are determined, each person will move to one of the vertices $$$v_1$$$, $$$\ldots$$$, $$$v_X$$$ with the minimum teleport distance to it. Let us define the meeting cost for the given $$$X$$$ and $$$i$$$ as the maximum of teleport distances for meeting participants. We will select the vertices $$$v_1$$$, $$$\ldots$$$, $$$v_X$$$ in such a way that the meeting cost is minimal possible.
The value of $$$X$$$ depends on the coronavirus situation, and may vary from $$$1$$$ to $$$K$$$. To prepare for the meeting in advance, write a program that, for each of the $$$N$$$ meetings, finds the sum of the meeting costs for all possible values of $$$X$$$ from $$$1$$$ to $$$K$$$, inclusive.
InputThe first line of input contains two integers $$$N$$$ and $$$K$$$: the number of vertices and the upper limit for $$$X$$$, respectively ($$$1 \leq K \leq N \leq 3 \cdot 10^5$$$).
The following $$$N - 1$$$ lines describe the tree. Each of these lines contains three integers, $$$A_i$$$, $$$B_i$$$, and $$$C_i$$$, telling that there is an edge between vertices $$$A_i$$$ and $$$B_i$$$ with weight $$$C_i$$$ ($$$1 \leq A_i, B_i, C_i \leq N$$$). It is guaranteed that the resulting graph is a tree.
OutputPrint $$$N$$$ lines. On line $$$i$$$, print the sum of meeting costs of $$$i$$$-th meeting for all $$$X$$$ from $$$1$$$ to $$$K$$$, inclusive.
ExamplesInput10 4 5 1 2 1 6 4 6 2 1 2 8 9 8 3 5 3 4 8 4 10 9 10 9 8 9 7 7Output
0 4 13 21 23 23 30 31 33 34Input
8 3 7 3 4 4 5 2 3 6 1 6 8 6 8 5 1 2 5 8 1 5 2Output
0 8 14 16 16 16 18 18