P5984 [PA 2019] Road Taxes

Given an unrooted tree with $n$ nodes, numbered from $1$ to $n$. The weight of every edge is a positive integer power of $n$. Define the distance $\operatorname{d(u,v)}$ from $u$ to $v$ as the sum of edge weights along the unique simple path between $u$ and $v$ in the tree. Given $k$, among the $\dfrac{n\times (n-1)}{2}$ values $\operatorname{d(u,v)}(1\le u

The first line contains two positive integers $n, k$. The next $n-1$ lines each contain three positive integers $x, y, z(1\le x, y, z\le n)$, indicating an edge connecting $x$ and $y$ with weight $n^z$.

Output one integer: the $k$-th smallest value modulo $10^9+7$.

For $100\%$ of the testdata, $2\le n\le 2.5\times 10^4$, and $1\le k\le \dfrac{n*(n-1)}{2}$. --- ### Sample Explanation After sorting all $d$, we get, in order: $5, 5, 25, 30, 125, 130, 130, 135, 150, 155$. Translated by ChatGPT 5