Ehab and a component choosing problem

题意翻译

## Description 给定一棵 $n$ 个节点的树，点有点权 $a_u$，可能为负。现在请你在树上找出 $k~(1~\leq~k~\leq~n)$ 个不相交集合，使得每个集合中的每对点都可以通过本集合中的点互相到达，假设选出的 $k$ 个集合的并集为 $s$，要求最大化： $$\frac{\sum_{u \in s} a_u}{k}$$ 如果有多解请输出 $k$ 最大的解 ## Input 第一行是节点个数 $n$。 下面一行 $n$ 个数代表点权 下面 $n - 1$ 行描述这棵树 ## Output 输出一行两个整数，分别是选出的点权和以及 $k$ **不约分** Translated by @ 一扶苏一

题目描述

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.

输入输出样例

输入样例 #1

3
1 2 3
1 2
1 3

输出样例 #1

6 1

输入样例 #2

1
-2

输出样例 #2

-2 1

输入样例 #3

3
-1 -1 -1
1 2
2 3

输出样例 #3

-3 3

输入样例 #4

3
-1 -2 -1
1 2
1 3

输出样例 #4

-2 2

说明

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.