Tree Master solution codechef
For Solution

Click Here!

Given is a tree with $N$ weighted vertices and $N - 1$ weighted edges. The $i$ -th vertex has a weight of $A_{i}$ . The $i$ -th edge has a weight of $W_{i}$ and connects vertices $u_{i}$ and $v_{i}$ .

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 $i$ -th query, you are given two integers $x_{i}$ and $y_{i}$ and you need to compute:

\sum k \in V (x i, y i) (dist (x i, k) - dist (k, y i)) \cdot A k

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 $N$ integers $A_{1}, A_{2}, \dots, A_{N}$ .
Each of the next $N - 1$ lines contains three integers $u_{i}$ , $v_{i}$ and $W_{i}$ .
Each of the next $Q$ lines contains two integers $x_{i}$ and $y_{i}$ .

Output Format

For each query, print the answer to it on a new line.

Constraints

$1 \leq T \leq 10^{3}$
$2 \leq N \leq 2 \cdot 10^{5}$
$1 \leq Q \leq 2 \cdot 10^{5}$
$1 \leq A_{i}, W_{i} \leq 10^{4}$
$1 \leq u_{i}, v_{i}, x_{i}, y_{i} \leq N$
$x_{i} \neq y_{i}$
$u_{i} \neq v_{i}$
The sum of $N$ across all test cases does not exceed $2 \cdot 10^{5}$ .
The sum of $Q$ across all test cases does not exceed $2 \cdot 10^{5}$ .

Subtasks

Subtask #1 (20 points): $u_{i} = i, v_{i} = 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 \cdot (0 - 5) + 3 \cdot (1 - 4) + 5 \cdot (3 - 2) + 2 \cdot (5 - 0) = 1$
For the second query, $V (5, 4) = {5, 1, 2, 4}$ . The answer is $2 \cdot (0 - 5) + 5 \cdot (2 - 3) + 3 \cdot (4 - 1) + 1 \cdot (5 - 0) = - 1$

For Solution

Click Here!

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.