A12173 | Ehab and a component choosing problem

You're given a tree consisting of $n$ nodes. Every node $u$ has a weight $a_u$ . You want to choose an integer $k$ $(1 \le k \le n)$ and then choose $k$ connected components of nodes that don't overlap (i.e every node is in at most 1 component). Let the set of nodes you chose be $s$ . You want to maximize:

$$$$\frac{\sum\limits_{u \in s} a_u}{k} $$ </p><p>In other words, you want to maximize the sum of weights of nodes in $s$ divided by the number of connected components you chose. Also, if there are several solutions, you want to <span class="tex-font-style-bf">maximize $k$$$.

Note that adjacent nodes can belong to different components. Refer to the third sample.

The first line contains the integer $n$ $(1 \le n \le 3 \cdot 10^5)$ , the number of nodes in the tree.

The second line contains $n$ space-separated integers $a_1$ , $a_2$ , $\dots$ , $a_n$ $(|a_i| \le 10^9)$ , the weights of the nodes.

The next $n-1$ lines, each contains 2 space-separated integers $u$ and $v$ $(1 \le u,v \le n)$ which means there's an edge between $u$ and $v$ .

Print the answer as a non-reduced fraction represented by 2 space-separated integers. The fraction itself should be maximized and if there are several possible ways, you should maximize the denominator. See the samples for a better understanding.