You are given N nodes. There are N -1 connecting edges between any two nodes Each node has a value denoted by an array A
Write a program to divide the tree along an edge i so as to minimize the difference between the sums of the node values on either side of the element
Example
Consider N=3 ,edges-(1-2),(2-3) and A-10, 5, 20 You must determine the edge to be deleted that meets the following
conditions
If you delete the 1st edge 1-2 then the sum of difference would be abs(10-25) = 15.
If you delete the 2nd edge 2-3, then the sum of difference would be abs(15-20) = 5
Thus the minimum value is 5 when you delete the 2nd edge which is 2-3 Hence the answer is 5
Constraints
1 ≤ T ≤ 10
2≤ N ≤ 10^5
1 ≤ Ai ≤ 10^5
1≤ Ui, Vi ≤ N