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

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.

给你一棵包含 $n$ 个节点的树。每个节点 $u$ 都有一个权值 $a_u$。你需要选择一个整数 $k$（满足 $1 \le k \le n$），然后选出 $k$ 个互不相交（即每个节点至多属于其中一个连通块）的连通块。设你所选的所有节点构成的集合为 $s$。你的目标是最大化以下表达式：

$$\frac{\sum\limits_{u \in s} a_u}{k}$$

换言之，你要最大化所选节点的权值总和与所选连通块数量 $k$ 的比值。此外，若存在多个最优解，则在其中进一步最大化 $k$。

注意：相邻的节点可以属于不同的连通块。参见第三个样例。

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

第一行包含一个整数 $n$ $(1 \le n \le 3 \cdot 10^5)$，表示树中节点的数量。

第二行包含 $n$ 个以空格分隔的整数 $a_1$, $a_2$, $\dots$, $a_n$ $(|a_i| \le 10^9)$，表示各节点的权值。

接下来的 $n-1$ 行，每行包含两个以空格分隔的整数 $u$ 和 $v$ $(1 \le u,v \le n)$，表示节点 $u$ 与节点 $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.

以一个未约分的分数形式输出答案，该分数由两个用空格分隔的整数表示。该分数本身应尽可能大；若存在多种可能，则应使分母尽可能大。参见样例以获得更清晰的理解。

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.

连通分量是指一个节点集合，使得该集合中任意一个节点都可以仅通过该集合内的节点到达集合中的所有其他节点。

在第一个样例中，选择整棵树是最优的。

在第二个样例中，你只有一种选择（即仅选择节点 1），因为你不能选择 0 个连通分量。

在第三个样例中，请注意：例如，我们可以仅选择节点 1，或选择节点 1 和节点 3，甚至选择整棵树，此时分数值都相同（均为 $-1$），但我们的目标是最大化 $k$。

在第四个样例中，我们仅选择节点 1 和节点 3。