Problem Description

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.

Input Format

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 Format

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

6 6
2 1 1
5 1 1
3 1 3
4 5 1
6 3 3
2 5
1 5
1 4
3 6
2 6
1 1

19
26
18
28
44
0

Hint

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