Mister IP found a graph in his yard. After some inspection, he realized that this graph is a tree! Moreover, each vertex had a beauty parameter a_i assigned to it!
He wants to decorate his room with this tree, but since using it whole may be ugly, he will slice it into components by doing the following exactly once:
pick a vertex in the tree
remove from the tree, leaving some connected components. Mister IP will use those to decorate his room.
Suppose there are components left after the slice.
We define the centroid of a component of size to be the vertex with the largest value of a_v among all vertices that satisfy the following property:
if is removed from the component, it breaks into smaller components of sizes at most \frac{m}{2}.
Let c_1, c_2, \dots, c_k be the centroids of the resulting components. The beauty of such a slice is calculated as the sum a_{c_1} + a_{c_2} + \dots + a_{c_k}.
Find any vertex that maximizes the beauty of the slice, and calculate the beauty it achieves!
The first line contains a single integer (3 \le n \le 3 \cdot 10^5) — the number of vertices in the tree.
The second line contains integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^9) — the beauty parameters of vertices.
The next n-1 lines contain the description of the tree: the i+2-th line of input contains two integers u_i and v_i (1 \le u_i, v_i \le n) — the -th edge of the tree.
It is guaranteed that the input describes a valid tree.
Output two integers and — the index of the vertex used in the slice that achieves maximum beauty, and the value of the beauty of this slice.
Example 1
Example 2
In the first sample, for each choice of "slice" vertex:
u = 1, centroids of the two components are and , with the beauty of 2+3 = 5.
u = 2, three centroids are , and , with the beauty of 4+5+3 = 12.
u = 3, three centroids are , and , with total beauty 6+7+2 = 15.
For u=4,5, a single centroid is with beauty .
For u=6,7, a single centroid is with beauty .
In the second sample, by slicing at vertex , three components are formed: \{1\}, \{4\}, \{2,5,6\} with centroids and beauty 4+1+6=11.
( points): a_i = 1 for all ;
( points): u_i = i; v_i = i+1;
( points): n \le 50;
( points): n \le 10^3;
( points): n = 2^k-1; u_i = \lfloor \frac{i+1}{2} \rfloor; v_i = i+1;
( points): no additional constraints.