题目描述
题目译自 PA 2019 Runda 5 Podatki drogowe
给定一棵 n 个点的无根树,点的编号为 1 到 n。第 i 条边连接点 ai 和 bi,边权为 npi。
定义 u 到 v 的距离 d(u,v) 为 u 和 v 在树上的简单路径的边权之和。
给定 k,请在 2n(n−1) 个 d(u,v)(1≤u<v≤n)中找到第 k 小的值。
输入格式
第一行两个正整数 n,k。
接下来 n−1 行,每行三个正整数 ai,bi,pi,表示一条连接 ai 和 bi 的边,其边权为 npi。
输出格式
输出一行一个整数,即第 k 小的值对 109+7 取模的结果。
样例
5 8
1 2 1
3 1 3
3 4 1
5 3 2
135
所有的 d(u,v) 有:5,5,25,30,125,130,130,135,150,155,第 8 小的为 135,是 u=2,v=4 这条路径。
数据范围与提示
2≤n≤25000,1≤k≤2n(n−1),1≤ai,bi,pi≤n