Google OA-1 2023

Problem Description

You are presented with an undirected tree consisting of N nodes, each assigned a specific value. Your task is to partition these nodes into the smallest number of groups possible, ensuring that no two adjacent nodes are included in the same group.

For any group G, consider a pair of nodes (u, v) within that group. The value of this pair is calculated as |A[u] - A[v]|, where A represents the values assigned to the nodes (1 ≤ x ≤ N).

The cost of group G is defined as the highest sum achievable by pairing the nodes within the group, with the possibility that some nodes may remain unpaired.

Your objective is to determine the total cost for all potential groups that can be formed from the given tree.

Input format
The first line has an integer T 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 A[1], A[2], ..., A[n].
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.
The cost of the group G'1 turns out to be |12 - 13| = 1, by pairing nodes 1 and 4.
G2: Nodes 2 and 3 can be grouped together. Pairing Nodes 2 and 3, we get the value as |17 - 14| = 3. The final answer is cost(G1) + cost(G2) = 4