Sum of Sums
Given a undirected tree containing N nodes where i^{th} 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
a_{1}, a_{2}, ..., a_{N}, where
a_{i} (1 ≤
a_{i} ≤ $$10^6$$) is the value stored at the
i^{th} 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.
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:
C,
C++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Scala 2.11.8,
Swift,
Visual Basic