Instability of a Tree#1178
Given a tree with nodes. Each node has an associated value c_u. The instability of a rooted tree is defined as:
Here, L_i denotes the level of node with respect to the root. The root is at level . You must choose the root of the tree in such a way that the instability value is minimized.
The first line contains the number of test cases . For each test case, the first line contains an integer , the number of nodes in the tree. The next line contains space-separated integers, where the -th integer is the value c_i of the -th node. Each of the following N-1 lines contains two integers and (1 \leq a, b \leq N), describing an edge between nodes and .
It is guaranteed that 1 \leq T \leq 20, 1 \leq N \leq 20000, 1 \leq c_i \leq 1000.
Output lines. Each line should contain the minimum possible instability value for the corresponding test case.
Example 1