#P5550. [PA2019]Podatki drogowe

    ID: 4553 传统题 7000ms 768MiB 尝试: 3 已通过: 2 难度: 10 上传者: 标签>CF2900省选/NOI-点分治点分治容斥去重可持久化线段树路径复制随机哈希相向双指针随机采样单调判定

[PA2019]Podatki drogowe

[PA2019] Podatki drogowe

题目描述

给定一棵 nn 个点的无根树,点的编号为 11 到 nn。 定义 uu 到 vv 的距离 d(u,v)⁡\operatorname{d(u,v)} 为 uu 和 vv在树上的简单路径经过的边的边权之和。

给定 kk,请在 n×(n−1)2\dfrac{n\times (n-1)}{2} 个 d(u,v)⁡(1≤u<v≤n)\operatorname{d(u,v)}(1\le u<v\le n) 中找到第 kk 小的值。

输入格式

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

接下来 n−1n-1 行,每行三个正整数 x,y,z(1≤x,y,z≤n)x,y,z(1\le x,y,z\le n),表示一条连接 xx 和 yy 的树边,其边权为 nn 的 zz 次方。

输出格式

输出一行一个整数,即第 kk 小的值对 109+710^9+7 取模的结果。

样例 #1

样例输入 #1

5 8
1 2 1
3 1 3
3 4 1
5 3 2

样例输出 #1

135

提示

对于 100%100\% 的数据,2≤n≤2.5×1042\le n\le 2.5\times 10^4,1≤k≤n∗(n−1)21\le k\le \dfrac{n*(n-1)}{2}。


样例解释:

所有的 dd 排序后依次为: 5,5,25,30,125,130,130,135,150,1555,5,25,30,125,130,130,135,150,155。