Городские олимпиады/1-2 курсы/Предметная олимпиада по информатике 2019


8. Недовольство от молока (200 баллов)

Автор задачи: Ицков Алексей
Ограничение по времени: 1 с.
Ограничение по памяти: 256 МБ

Петр, имея свою собственную фабрику молока, живет в стране, в которой находятся n городов. Карта страны выглядит в виде дерева: некоторые пары городов соединены дорогой расстоянием в 1 единицу, при этом между любыми двумя городами существует один единственный путь.

Каждый город имеет свой показатель недовольства a_i, который умножается на расстояние от стартового города. Требуется выбрать один из городов стартовым, чтобы суммарное недовольство всех городов было минимальным.

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

Первая строка содержит одно целое число n — количество городов (2 \leqslant n \leqslant 10^5).

В следующей строке находятся n целых чисел a_i — недовольство города под номером i (0 \leqslant a_i \leqslant 10^5).

В следующих n-1 строках находятся пары чисел u, v, которые означают что между городом u и городом v есть дорога (1 \leqslant u, v \leqslant n). Все пары различны.

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

Требуется вывести 2 числа — номер города, при котором суммарное недовольство минимально, и само суммарное недовольство. Если правильных ответов несколько, то разрешается вывести любой.

Примеры
Стандартный вводСтандартный вывод
4
1 2 3 4
1 2
2 3
1 4
1 12
7
3 5 2 4 6 0 0
1 2
2 3
2 4
2 5
5 6
5 7
2 15
Примечания

Решения, правильно работающие при 2 \leqslant n \leqslant 5 \cdot 10^3, будут оцениваться из 60 баллов.

Решения, правильно работающие при 2 \leqslant n \leqslant 10^5, будут оцениваться из 200 баллов.