Codeforces Round 525 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

greedy

math

trees

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Ehab and a component choosing problem

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou'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}$$$$$$

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 maximize $$$k$$$.

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

Input

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$$$.

Output

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.

Examples

Input

3 1 2 3 1 2 1 3

Output

6 1

Input

1 -2

Output

-2 1

Input

3 -1 -1 -1 1 2 2 3

Output

-3 3

Input

3 -1 -2 -1 1 2 1 3

Output

-2 2

Note

A connected component is a set of nodes such that for any node in the set, you can reach all other nodes in the set passing only nodes in the set.

In the first sample, it's optimal to choose the whole tree.

In the second sample, you only have one choice (to choose node 1) because you can't choose 0 components.

In the third sample, notice that we could've, for example, chosen only node 1, or node 1 and node 3, or even the whole tree, and the fraction would've had the same value (-1), but we want to maximize $$$k$$$.

In the fourth sample, we'll just choose nodes 1 and 3.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/07/2023 03:44:24 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|