Вам дано дерево, состоящее из \(n\) вершин. Каждая вершина \(u\) имеет некоторый вес \(a_u\). Вы хотите выбрать целое число \(k\) \((1 \le k \le n)\), а затем выбрать \(k\) связных компонент, которые не пересекаются друг с другом (каждая вершина находится максимум в одной компоненте). Пусть вы выбрали компоненты, в совокупности содержащие множество вершин \(s\). Вы хотите максимизировать следующее значение:
\(\)\frac{\sum\limits_{u \in s} a_u}{k}\(\)
Другими словами, вы хотите максимизировать сумму весов вершин из \(s\), деленную на количество выбранных вами компонент. Также, если возможных решений несколько, вы хотите максимизировать \(k\).
Заметьте, что соседние вершины могут находиться в разных компонентах. Для лучшего понимания обратитесь к третьему тесту.
Выходные данные
Выведите ответ как несокращенную дробь, выраженную двумя целыми числами (первое из них является числителем дроби, второе - знаменателем). Дробь должна быть максимально возможной, а при равенстве необходимо максимизировать знаменатель. Для лучшего понимания обратитесь к примерам из условия.
Примечание
Связная компонента - это множество вершин, что для любой пары вершин из множества существует путь между этими вершинами только по вершинам множества.
В первом примере оптимально выбрать все дерево.
Во втором примере есть только один вариант выбора (выбрать компоненту, содержащую единственную вершину 1) потому что нельзя выбирать 0 компонент.
В третьем примере следует заметить, что можно было выбрать, например, только вершину 1 или вершины 1 и 3, или все дерево, и результирующая дробь во всех этих случая имела бы значение -1, но необходимо максимизировать \(k\).
В четвертом примере оптимально выбрать вершины 1 и 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
1 2
1 3
|
6 1
|
|
2
|
1
-2
|
-2 1
|
|
3
|
3
-1 -1 -1
1 2
2 3
|
-3 3
|
|
4
|
3
-1 -2 -1
1 2
1 3
|
-2 2
|