SOLVE

LATER

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.

The second line contains

The next

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.

- \( 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

Initializing Code Editor...