给你一棵由 $$$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。