Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21622. 【ExPR #1】守卫 2

Statistics

在 P 国有 $n$ 个村子,以及 $n-1$ 条待修建的双向公路,第 $i$ 条公路连接 $u_i,v_i$,修建的代价为 $c_i$,保证任意两个村子可以通过一些双向公路互相到达。

已知国王和 $k$ 个守卫在某个村子 $r$,第 $i$ 个守卫需要到达某个村子 $x_i$。

国王会选择代价之和尽可能少的一些公路进行修建,使得每个守卫可以从 $r$ 出发经过这些公路到达目的地。

对于每个 $r\in[1,n]$,求在所有选择 $x_i\in[1,n]$ 的情况下,国王修建公路所需代价之和的最大值。

输入格式

第一行,两个正整数 $n,k$。

之后 $n-1$ 行,每行两个正整数 $u_i,v_i$ 和一个非负整数 $c_i$。

输出格式

共 $n$ 行,第 $r$ 行一个非负整数,表示对应的答案。

样例一

input

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

output

28
28
28
32
30
32
28
32
32
29
30

explanation

图论可视化工具:https://csacademy.com/app/graph_editor/

例如对于 $r=1$ 的情况,当 $x_1=4$,$x_2=6$,$x_3=9$ 时国王需要修建代价之和为 $28$ 的公路,且可以证明不会有代价更大的情况。

样例二

见下发文件,该样例符合子任务 $4$ 的限制。

数据范围与提示

对于所有数据,$1\le k\le n\le 10^5$,$0\le c_i\le 10^9$。

子任务编号 特殊限制 分值
$1$ $n\le 18$ $8$
$2$ $n\le 200$,$k\le 20$ $11$
$3$ $n\le 1000$,$k\le 100$ $17$
$4$ $n\le 2000$ $20$
$5$ $k=1$ $12$
$6$ $ $ $32$

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$