Instability of a Tree
Given a tree with N nodes. Each node u of the tree has an associated cost c_u. We define the instability of a rooted tree to be:
Here L_i is the level of the node i with respect to the root of the tree. Root is assumed to be at level 0. You are required to find a root such that minimizes the instability value.
Input
First line contains an integer T, the number of test cases. Each test case begins with an integer N, the number of nodes in the tree. The next line contains N space separated integers where the i-th integer represents the cost of the i-th node of the tree. The following N-1 lines contain two space separated integers a b (1 ≤ a, b ≤ N) representing an edge between node a and b.
It is known that 1 ≤ T ≤ 20, 1 ≤ N ≤ 20000, 1 ≤ c_i ≤ 1000.
Output
Output T lines. Each line containing the minimum instability value for the corresponding test case.