P7581 "RdOI R2" Path Weight (distance)

This problem has a large amount of input. Please choose an appropriate input method.

You are given a rooted tree with $n$ nodes and weighted edges. The root is node $1$. Define the $k$-son of a node $u$ as all nodes in the subtree of $u$ whose depth (number of edges on the path) is **exactly** $k$ greater than that of $u$. There are $m$ queries. For each query, compute the sum of distances between every pair of nodes among the $k$-sons of a node $u$. You need to output the result modulo $\bmod\left(10^9+7\right)$.

The first line contains two integers $n, m$. The next $n - 1$ lines each contain three integers $u, v, w$, indicating that there is an edge of weight $w$ between $u$ and $v$. The next $m$ lines each contain two integers $u, k$, indicating a query.

For each query, output one line containing the answer.

**Sample $1$ Explanation** Below is the tree in the sample.  --- **Sample $2$ Explanation** Below is the tree in the sample.  --- **Constraints** For $20\%$ of the testdata, $n, m, k \le 100$. For $50\%$ of the testdata, $n, m, k \le 10^3$. For $80\%$ of the testdata, $n, m, k \le 10^5$. For $100\%$ of the testdata, $1 \le n, m, k \le 10^6$, $1 \le k \le n$, $1 \le w \le 10^5$, $1 \le u, v \le n$. It is guaranteed that the given graph is a tree. Translated by ChatGPT 5