#BZOJ4317. Atm的树
-
ID: 2917
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
Atm的树
No submission language available for this problem.
题目描述
Atm有一段时间在虐qtree的题目，于是，他满脑子都是tree，tree，tree……
于是，一天晚上他梦到自己被关在了一个有根树中，每条路径都有边权，一个神秘的声音告诉他，每个点到其他的点有一个距离（什么是距离不用说吧），他需要对于每个点回答：从这个点出发的第k小距离是多少；
如果atm不能回答出来，那么明天4019的闹钟将不会响，4019全寝可能就迟到了，所以atm希望你帮帮他。
输入格式
第一行，两个正整数n，k，表示树的点数，询问的是第几小距离；
第二~n行，每行三个正整数x，y，w，表示x和y之间有一条边，x为父亲，边权为w；
输出格式
n行， 每行一个数，第i行输出从i开始第k小距离
5 2
1 5 2
1 2 4
2 3 6
2 4 5
4
5
10
9
6
数据范围与约定
100% n<=15000, 边权在1~10之间，为了方便，保证1为根；K<=5000