7596: Distance

You are given a tree with n nodes, each edge of the tree has a weight, the nodes of the tree are numbered from 1 to n .

Let dist(i,j) be the sum of edges' weight on the path between i and j .

You need to answer m queries, each query is given l,r , you are asked to output the sum of all dist(i,j) , that satisfies l≤i<j≤r .

The input contains several test cases, and the first line contains a single integer T , the number of test cases.

For each test case:

The first line contains two integers n,m .

For the following n−1 lines, each line contains three integers u,v,d , which means that there is an edge between u,v , the weight of this edge is d .

For the following m lines, each line contains two integers l,r , which means that there is a query for l,r .

1≤T≤3 ，1≤n,m,d≤2⋅105 , l≤r , all input are integers.

For each test case, output m lines representing the answer for the given m queries.

You need to output the answer module 232 .

3
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
6 6
2 1 3
3 1 2
4 3 1
5 1 1
6 3 3
2 4
2 4
1 1
1 6
1 4
1 1
6 6
6 5 2
1 6 3
4 1 1
3 5 2
2 4 3
5 5
1 3
1 1
3 4
4 5
1 1

19
26
18
28
44
0
12
12
0
58
20
0
0
22
0
8
6
0