← 返回题目列表

Codeforces · 1088/E

E. Ehab 和组件选择问题

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 节点组成的树。每个节点 $$$u$$$ 都有一个权重 $$$a_u$$$。您想要选择一个整数 $$$k$$$ $$$(1 \le k \le n)$$$,然后选择不重叠的节点的 $$$k$$$ 连接组件(即每个节点最多位于 1 个组件中)。让您选择的节点集为$$$s$$$。你想要最大化:

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

换句话说,您希望最大化 $$$s$$$ 中节点的权重总和除以您选择的连接组件的数量。另外,如果有多个解决方案,您希望最大化 $$$k$$$。

请注意,相邻节点可以属于不同的组件。请参阅第三个示例。

输入

第一行包含整数 $$$n$$$ $$$(1 \le n \le 3 \cdot 10^5)$$$,即树中的节点数。

第二行包含 $$$n$$$ 以空格分隔的整数 $$$a_1$$$、$$$a_2$$$、$$$\dots$$$、$$$a_n$$$ $$$(|a_i| \le 10^9)$$$,即节点的权重。

接下来的 $$$n-1$$$ 行,每行包含 2 个空格分隔的整数 $$$u$$$ 和 $$$v$$$ $$$(1 \le u,v \le n)$$$,这意味着 $$$u$$$ 和 $$$v$$$ 之间有一条边。

输出

将答案打印为由 2 个空格分隔的整数表示的非约分数。分数本身应该最大化,如果有多种可能的方法,您应该最大化分母。请参阅示例以更好地理解。

示例

输入 #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

注意

连接组件是一组节点,对于该组中的任何节点,您可以仅通过该组中的节点到达该组中的所有其他节点。

在第一个示例中,最好选择整棵树。

在第二个示例中,您只有一个选择(选择节点 1),因为您不能选择 0 个组件。

在第三个示例中,请注意,例如,我们可以仅选择节点 1,或节点 1 和节点 3,甚至整个树,并且分数将具有相同的值 (-1),但我们希望最大化 $$$k$$$。

在第四个示例中,我们将仅选择节点 1 和 3。