Problem Description

Given a tree with $n$ nodes, the root is $1$. Each node has an index, and each edge has a weight.

Define $dep(x)$ as the sum of edge weights on the simple path from node $x$ to the root, and $lca(x,y)$ as the lowest common ancestor of nodes $x$ and $y$ in the tree.

There are $m$ queries. In each query, $l,r$ are given. For all ordered pairs of node indices $(i,j)$ satisfying $l \le i,j \le r$, ask how many distinct values of $dep(lca(i,j))$ there are.

Input Format

The first line contains two integers $n,m$ separated by spaces.

The next $n-1$ lines each contain three integers $u,v,d$ separated by spaces, meaning there is an edge from $u$ to $v$ with weight $d$.

The next $m$ lines each contain two integers $l,r$ separated by spaces, representing one query.

Output Format

Output $m$ lines. Each line contains one integer, the answer to the corresponding query.

10 19
9 1 -4
9 8 2
8 10 5
9 7 -3
1 4 2
10 2 5
10 5 -1
7 3 -3
10 6 5
8 10
4 6
1 7
7 9
5 5
7 8
8 10
10 10
10 10
9 10
5 7
8 8
6 6
2 8
9 10
4 8
5 5
1 6
1 2

3
4
7
3
1
3
3
1
1
2
5
1
1
8
2
7
1
6
2

10 19
6 1 299830931
1 4 -565297395
1 7 -606073228
4 8 94253706
8 9 -576603423
4 3 116780102
3 5 620388954
7 10 -950023905
5 2 813045783
3 5
7 7
8 10
4 7
10 10
9 9
4 7
8 10
6 7
4 8
9 10
2 9
8 10
2 8
4 4
10 10
4 9
1 5
8 9

3
1
4
5
1
1
5
4
3
6
3
9
4
8
1
1
7
5
2

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: lk, Data: nzhtl1477.

Constraints:

For $10\%$ of the testdata, $1 \le n,m \le 100$.

For another $20\%$ of the testdata, $1 \le n,m \le 5000$.

For another $20\%$ of the testdata, $1 \le n,m \le 50000$.

For another $20\%$ of the testdata, $d=1$.

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 5 \times 10^5$, all values are integers, and $-10^9 \le d \le 10^9$.

Translated by ChatGPT 5