「PA 2019」道路数据

题目描述

题目译自 PA 2019 Runda 5 Podatki drogowe

给定一棵 $n$ 个点的无根树，点的编号为 $1$ 到 $n$ 。第 $i$ 条边连接点 $a_i$ 和 $b_i$ ，边权为 $n^{p_i}$ 。

定义 $u$ 到 $v$ 的距离 $d(u, v)$ 为 $u$ 和 $v$ 在树上的简单路径的边权之和。

给定 $k$ ，请在 $\frac{n(n-1)}{2}$ 个 $d(u, v)$ （ $1 \le u < v \le n$ ）中找到第 $k$ 小的值。

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

接下来 $n - 1$ 行，每行三个正整数 $a_i, b_i, p_i$ ，表示一条连接 $a_i$ 和 $b_i$ 的边，其边权为 $n^{p_i}$ 。

输出一行一个整数，即第 $k$ 小的值对 $10^9+7$ 取模的结果。

样例解释：
所有的 $d(u, v)$ 有： $5, 5, 25, 30, 125, 130, 130, 135, 150, 155$ ，第 $8$ 小的为 $135$ ，是 $u=2, v=4$ 这条路径。

$2 \le n \le 5 \times 10^4$

$1 \le k \le \frac{n(n-1)}{2}$

$1 \le a_i, b_i \le n$

$1 \le p_i \le 10^9$