|
||||||||||
DistanceTime Limit: 15000/15000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 63 Accepted Submission(s): 16 Problem Description 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 $\texttt {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 $\texttt {dist}(i,j)$, that satisfies $l \le i<j \le r$. Input 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 \le T \le 3$£¬$1\le n,m,d\le 2\cdot 10^5$, $l \le r$, all input are integers. Output For each test case, output $m$ lines representing the answer for the given $m$ queries. You need to output the answer module $2^{32}$. Sample Input
Sample Output
Source | ||||||||||
|