E. Ехаб и задача о выборе компонент
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево, состоящее из $$$n$$$ вершин. Каждая вершина $$$u$$$ имеет некоторый вес $$$a_u$$$. Вы хотите выбрать целое число $$$k$$$ $$$(1 \le k \le n)$$$, а затем выбрать $$$k$$$ связных компонент, которые не пересекаются друг с другом (каждая вершина находится максимум в одной компоненте). Пусть вы выбрали компоненты, в совокупности содержащие множество вершин $$$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$$$ строка, в каждой из которых содержатся по два целых числа$$$u$$$ и $$$v$$$ $$$(1 \le u,v \le n)$$$. Это означает, что между $$$u$$$ и $$$v$$$ есть ребро в данном дереве.

Выходные данные

Выведите ответ как несокращенную дробь, выраженную двумя целыми числами (первое из них является числителем дроби, второе - знаменателем). Дробь должна быть максимально возможной, а при равенстве необходимо максимизировать знаменатель. Для лучшего понимания обратитесь к примерам из условия.

Примеры
Входные данные
3
1 2 3
1 2
1 3
Выходные данные
6 1
Входные данные
1
-2
Выходные данные
-2 1
Входные данные
3
-1 -1 -1
1 2
2 3
Выходные данные
-3 3
Входные данные
3
-1 -2 -1
1 2
1 3
Выходные данные
-2 2
Примечание

Связная компонента - это множество вершин, что для любой пары вершин из множества существует путь между этими вершинами только по вершинам множества.

В первом примере оптимально выбрать все дерево.

Во втором примере есть только один вариант выбора (выбрать компоненту, содержащую единственную вершину 1) потому что нельзя выбирать 0 компонент.

В третьем примере следует заметить, что можно было выбрать, например, только вершину 1 или вершины 1 и 3, или все дерево, и результирующая дробь во всех этих случая имела бы значение -1, но необходимо максимизировать $$$k$$$.

В четвертом примере оптимально выбрать вершины 1 и 3.