B'You, the monster killer, want to kill a group of monsters. The monsters are on a tree with n vertices. On vertex with number i ( 1 <= i <= n ), there is a monster with a_i attack points. You want to battle with monsters for 10^{100} rounds. In each round, the following happens in order: There is a restriction: in one round, you cannot kill two monsters that are directly connected by an edge. If you choose what monsters to attack optimally, what is the smallest health decrement you can have after all rounds? Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= t <= 10^4 ). Description of the test cases follows. The first line of each test case contains an integer n ( 1 <= n <= 3 cdot 10^5 ). The second line of each test case contains n integers a_1, ldots,a_n ( 1 <= a_i <= 10^{12} ). The following n-1 lines each contain two integers x,y ( 1 <= x,y <= n ), denoting an edge on the tree connecting vertex x and y . It is guaranteed that the sum of n over all test cases does not exceed 3 cdot 10^5 . For each test case, print one integer: the minimum possible health decrement. In the first test case, an optimal sequence of operations would be: The total health decrement is 10^{12} . In the second test case, an optimal sequence of operations would be: The total health decrement is 193 . In the third test case, an optimal sequence of operations would be: The total health decrement is 57 . '...