CF1088E Ehab and a component choosing problem

给定一棵包含 $n$ 个节点的树。每个节点 $u$ 有一个权值 $a_u$。你需要选择一个整数 $k$（$1 \le k \le n$），然后选择 $k$ 个互不重叠的连通块（即每个节点至多属于一个连通块）。设你选择的所有节点的集合为 $s$。你希望最大化以下表达式： $$ \frac{\sum\limits_{u \in s} a_u}{k} $$ 换句话说，你希望最大化所选节点权值之和与所选连通块数量之比。如果有多种方案能够取得最大值，你还需要**最大化 $k$**。 注意，相邻的节点可以属于不同的连通块，详见第三个样例。

第一行包含一个整数 $n$（$1 \le n \le 3 \times 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$ 之间有一条边。

输出最大值对应的分数，格式为两个用空格分隔的整数，分别表示分子和分母（不需要约分）。如果有多种方案取得最大值，分母应尽可能大。具体格式见样例。

一个连通块是指这样一个节点集合：对于集合中的任意两个节点，存在仅经过集合内节点的路径将它们连通。 在第一个样例中，最优方案是选择整棵树。 在第二个样例中，你只有一种选择（只能选节点 1），因为不能选择 0 个连通块。 在第三个样例中，注意你可以只选节点 1，或者选节点 1 和节点 3，甚至选整棵树，分数都是 $-1$，但我们要最大化 $k$。 在第四个样例中，最优方案是选择节点 1 和节点 3。 由 ChatGPT 4.1 翻译