bzoj#P4317. Atm的树

Atm的树

题目描述

Atm 有一段时间在虐 qtree 的题目,于是,他满脑子都是 tree,tree,tree……

于是,一天晚上他梦到自己被关在了一个有根树中,每条路径都有边权,一个神秘的声音告诉他,每个点到其他的点有一个距离,他需要对于每个点回答:从这个点出发的第 kk 小距离是多少;

如果 atm 不能回答出来,那么明天 4019 的闹钟将不会响,4019 全寝可能就迟到了,所以 atm 希望你帮帮他。

输入格式

第一行两个整数 n,kn,k 表示树的点数和询问的 kk

接下来 n1n-1 行,每行三个整数 u,v,wu,v,w 表示一条 uuvv 权值为 ww 的无向边。

输出格式

nn 行,第 ii 行一个整数表示从 ii 出发的第 kk 小距离。

5 2
1 5 2
1 2 4
2 3 6
2 4 5
4
5
10
9
6

数据规模与约定

对于 100%100\% 的数据,1n1.5×1041\leq n\leq 1.5\times 10^4k5×103k\leq 5\times 10^31w101\leq w\leq 1011 是树的根。