Tree Master solution codechef- 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.

  • Tree Master solution codechef

  • For Solution

    Click Here!

Given is a tree with NN weighted vertices and N1N−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:

kV(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 N1N−1 lines contains three integers uiuivivi 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

  • 1T1031≤T≤103
  • 2N21052≤N≤2⋅105
  • 1Q21051≤Q≤2⋅105
  • 1Ai,Wi1041≤Ai,Wi≤104
  • 1ui,vi,xi,yiN1≤ui,vi,xi,yi≤N
  • xiyixi≠yi
  • uiviui≠vi
  • The sum of NN across all test cases does not exceed 21052⋅105.
  • The sum of QQ across all test cases does not exceed 21052⋅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(05)+3(14)+5(32)+2(50)=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(05)+5(23)+3(41)+1(50)=1

Leave a Comment

Your email address will not be published.