Google OA 2023 - Cost of groups

You are given an undirected tree with I nodes. Each node of the tree is assigned a value You are required to divide the nodes into as little groups as possible, such that no two nodes in a group are adjacent to each other.

Consider a group G. Let us consider a pair(u, w) from the group. The value of the pair (u, v) is given as |Au - Av❘ where A, is value assigned to node x (1 ≤ x ≤ N).
The cost of group G is defined as the maximum sum that you can get by pairing up the nodes of G. Each node can be used only once to make a pair. It is possible for some nodes in G to be unpaired.

Find the sum of the costs of all possible groups that can be made for the given tree.

Input format
The first line has an integer I denoting the number of test cases.
The first line of each test case contains an integer N denoting the number of nodes.
The second line of each test case contains N space-separated integers denoting the value assigned to the nodes A1, A2, ..., An.
Next N - 1 lines of each test case contain two integers U and V denoting an edge between the nodes U and V.

Output format

For each test case, print an integer denoting the sum in a new line.

Constraints

1 ≤T≤ 10
1 ≤ N ≤ 10^5
1 ≤A[i] ≤10^9
1≤ U,V≤ N

Sample Input
1
5
12 17 14 13 16
1 2
1 3
1 5
2 4

Sample Output
4

Explanation

G1: Nodes 1 and 4 can be grouped together.
The cost of the group G'1 turns out to be |12 - 13| = 1, by pairing nodes 1 and 4.
G2: Nodes 2, 3, and 5 can be grouped together. Pairing Nodes 2 and 3, we get the value as |17 - 14| = 3.
Node 5 is left unpaired. Pairing Nodes 3 and 5, we get the value as |14 - 16| = 2. Node 2 Is left unpaired. Pairing Node 2 and 5. we get value as |17 - 16| = 1. Node 3 is left unpaired. The cost of the group G2 turns out to be 3.
The final answer is cost(G1) + cost(G2) = 4