Tree Master TRMT Solution
Given is a tree with N weighted vertices and N−1 weighted edges. The i-th vertex has a weight of Ai. The i-th edge has a weight of Wi and connects vertices ui and vi.
Let dist(x,y) be the sum of weights of the edges in the unique simple path connecting vertices x and y.
Let V(x,y) be the set of vertices appearing in the unique simple path connecting vertices x and y (including x and y).
You are asked Q queries. In the ii-th query, you are given two integers xi and yi and you need to compute:∑k∈V(xi,yi)(dist(xi,k)−dist(k,yi))⋅Ak
Input Format
- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line contains two integers N and Q.
- The second line contains NN integers A1,A2,…,AN.
- Each of the next N−1 lines contains three integers ui, vi and Wi.
- Each of the next Q lines contains two integers xi and yi.
Output Format
For each query, print the answer to it on a new line.
Constraints
- 1≤T≤103
- 2≤N≤2⋅105
- 1≤Q≤2⋅105
- 1≤Ai,Wi≤104
- 1≤ui,vi,xi,yi≤N
- xi≠yi
- ui≠vi
- The sum of N across all test cases does not exceed 2⋅105
- The sum of Q across all test cases does not exceed 2⋅105
Subtasks
- Subtask #1 (20 points): ui=i,vi=i+1
- Subtask #2 (80 points): Original constraints
Sample Input 1
2
5 2
5 3 3 1 2
1 2 2
2 3 1
2 4 1
1 5 2
4 5
5 4
10 5
3 6 9 2 3 8 3 7 9 7
1 2 4
1 3 6
1 4 8
4 5 9
1 6 2
5 7 3
3 8 7
3 9 2
7 10 9
9 2
2 1
8 5
3 2
3 10
Sample Output 1
1
-1
-96
-12
-252
-24
-69
Explanation
Test Case 1:
- For the first query, V(4,5)={4,2,1,5}. The answer is 1⋅(0−5)+3⋅(1−4)+5⋅(3−2)+2⋅(5−0)=1
- For the second query, V(5,4)={5,1,2,4}. The answer is 2⋅(0−5)+5⋅(2−3)+3⋅(4−1)+1⋅(5−0)=−1