You are given an undirected tree with N nodes.
Each node of the tree is assigned to a value.
You are required to divide the nodes into as little groups as possible, such that no two nodes in the group are adjacent to each other.
Consider a group G. Let us consider a pair (u,v) from the group.
The value of pair (u,v) is given as |A[u] - A[v]| where A[x] is the value assigned to node x (1<=x<=n).
The cost of group G is defined as the maximum sum you can get by pairing up the nodes at 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 costs of all possible that can be made for the given tree.
Input Description
First line containing T - number of test cases.
First line of each test case containing N - number of nodes.
Second line of each test case containing N space separated integers denoting array A[].
Next N-1 lines contain U and V denoting an edge between the nodes U and V.
Example 1:
Input: n = 5, A = [12, 17, 14, 13, 16], edges = [[1, 2], [1, 3], [1, 5], [2, 4]]
Output: 4
Explanation:Group 1: Nodes 1 and 4 can be grouped together ->|12-13| = 1Group 2: Nodes 2, 3 and 5 can be grouped together. Pairing node 2 and 3 we get|17-14|=3, Pairing node 3 and 5 we get|14-16|=2, Pairing node 2 and 5 we get|17-16|=1. The maximum sum is obtained by pairing nodes 2 and 3. The cost of groupG1is1, and the cost of groupG2is3. Therefore, the sum of costs of all possible groups that can be made for the given tree iscost(G1) + cost(G2) = 1 + 3 = 4.
1 ≤ T ≤ 101 ≤ N ≤ 1051 ≤ A[i] ≤ 1091 ≤ U, V ≤ N
input:
output: