Problem Statement

You are given an undirected tree with N nodes. Each node of the tree is assigned a value. You are required to divide the nodes into as few groups as possible , such that no two nodes in a group are adjacent to each other. Consider a group G . Consider a pair (u, v) from the group. The value of the 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 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 costs of all the groups that are made for 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 . The next N − 1