-
Tree Master solution codechef
-
For Solution
Click Here!
Given is a tree with NN weighted vertices and N−1N−1 weighted edges. The ii-th vertex has a weight of AiAi. The ii-th edge has a weight of WiWi and connects vertices uiui and vivi.
Let dist(x,y)dist(x,y) be the sum of weights of the edges in the unique simple path connecting vertices xx and yy.
Let V(x,y)V(x,y) be the set of vertices appearing in the unique simple path connecting vertices xx and yy (including xx and yy).
You are asked QQ queries. In the ii-th query, you are given two integers xixi and yiyi and you need to compute:
∑k∈V(xi,yi)(dist(xi,k)−dist(k,yi))⋅Ak∑k∈V(xi,yi)(dist(xi,k)−dist(k,yi))⋅Ak
Input Format
- The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
- The first line contains two integers NN and QQ.
- The second line contains NN integers A1,A2,…,ANA1,A2,…,AN.
- Each of the next N−1N−1 lines contains three integers uiui, vivi and WiWi.
- Each of the next QQ lines contains two integers xixi and yiyi.
Output Format
For each query, print the answer to it on a new line.
Constraints
- 1≤T≤1031≤T≤103
- 2≤N≤2⋅1052≤N≤2⋅105
- 1≤Q≤2⋅1051≤Q≤2⋅105
- 1≤Ai,Wi≤1041≤Ai,Wi≤104
- 1≤ui,vi,xi,yi≤N1≤ui,vi,xi,yi≤N
- xi≠yixi≠yi
- ui≠viui≠vi
- The sum of NN across all test cases does not exceed 2⋅1052⋅105.
- The sum of QQ across all test cases does not exceed 2⋅1052⋅105.
Subtasks
- Subtask #1 (20 points): ui=i,vi=i+1ui=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 11:
- For the first query, V(4,5)={4,2,1,5}V(4,5)={4,2,1,5}. The answer is 1⋅(0−5)+3⋅(1−4)+5⋅(3−2)+2⋅(5−0)=11⋅(0−5)+3⋅(1−4)+5⋅(3−2)+2⋅(5−0)=1
- For the second query, V(5,4)={5,1,2,4}V(5,4)={5,1,2,4}. The answer is 2⋅(0−5)+5⋅(2−3)+3⋅(4−1)+1⋅(5−0)=−1
-
For Solution
Click Here!