BZPRO
#5550. [PA2019]Podatki drogowe
内存限制：768 MiB
时间限制：200 Sec
提交
提交记录
讨论
题目描述
给定一棵n个点的无根树，点的编号为1到n。
定义u到v的距离d(u,v)为u和v在树上的简单路径经过的边的边权之和。
给定k，请在n*(n-1)/2个d(u,v)(1<=u<v<=n)中找到第k小的值。
输入格式
第一行两个正整数n,k(2<=n<=25000,1<=k<=n*(n-1)/2)。
接下来n-1行，每行三个正整数x,y,z(1<=x,y,z<=n)，表示一条连接x和y的树边，其边权为n的z次方。
输出格式
输出一行一个整数，即第k小的值对10^9+7取模的结果。
样例
样例输入
5 8
1 2 1
3 1 3
3 4 1
5 3 2
样例输出
135
HINT
所有的d排序后依次为：5,5,25,30,125,130,130,135,150,155。
数据范围与提示
BZPRO