Sum of Sums
Tag(s):

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

This Problem was Asked in Challenge Name

October Circuits

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Math > Combinatorics
• Algorithms > Graphs
• Algorithms > Graphs
• Algorithms > Graphs
• Math > Basic Math