Sum of Sums
/

## Algorithms, Depth-first search, Graph, Medium-Hard

Problem
Editorial
Analytics

Given a undirected tree containing N nodes where ith node has value $a(i)$. Let us define cost of the tree as C, where
$C = \sum_{i=1}^N f(i)$
$f(i)=\sum_j g(j) ;where \hspace{0.25cm} j \hspace{0.25cm} \epsilon \hspace{0.25cm} subtree \hspace{0.25cm} of \hspace{0.25cm} i$
$g(j)=\sum_k a(k) ;where \hspace{0.25cm} k \hspace{0.25cm} \epsilon \hspace{0.25cm} subtree \hspace{0.25cm} of \hspace{0.25cm} j$
Find a root of the tree such that the cost of the tree is minimum.

### Input

The first line of input contains N (1 ≤ N ≤ 100,000) - the number of nodes in the tree.
The second line contains N integers a1, a2, ..., aN, where ai (1 ≤ ai$10^6$) is the value stored at the ith node.
The next N-1 lines contains two integers u and v, meaning that there is an edge connecting u and v.

### Output

Print two integers, the root of the tree such that the cost of tree is minimum and minimum cost. If there are multiple possible values of root, print the minimum one.

### Constraints

• $1 \leq N \leq 1000, 1 \leq a(i) \leq 10^6$ in 40% of test cases.
• $1 \leq N \leq 10^5, 1 \leq a(i) \leq 10^6$ in 60% of test cases.

NOTE: The value of C will fit in 64-bit integer.

SAMPLE INPUT
3
1 2 3
1 2
2 3
SAMPLE OUTPUT
2 14
Explanation

If root is 1 the cost C will be 25.
If root is 2 the cost C will be 14.
If root is 3 the cost C will be 15.
So the answer would be 2 14.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...