P6778 [Ynoi2009] rpdq

Given an undirected tree with $n$ nodes and weighted edges. Each node has a label, and the labels form a permutation of $1 \sim n$. There are $m$ queries. Each query gives $l, r$. You need to find the sum of distances on the tree over all pairs of node labels $(i, j)$ that satisfy $l \le i < j \le r$. The distance between two nodes is defined as the sum of edge weights along the simple path connecting them.

The first line contains two space-separated integers $n$ and $m$. The next $n-1$ lines each contain three space-separated integers $u$ $v$ $d$, meaning there is an edge between $u$ and $v$ with weight $d$. The next $m$ lines each contain two space-separated integers $l$ $r$, representing one query.

Output $m$ lines. Each line is the answer for the corresponding query, taken modulo $2^{32}$.

Idea: nzhtl1477, Solution: nzhtl1477, Code: zx2003, Data: nzhtl1477. For $100\%$ of the testdata, $1 \le n, m, d \le 2 \cdot 10^5$, and all values are integers. Translated by ChatGPT 5