B. Яблоня
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Дано корневое дерево, состоящее из n вершин. В каждом листе дерева записано ровно одно число — количество яблок в этом листе.

Весом поддерева назовем сумму чисел в листьях этого поддерева. В частности, вес поддерева, соответствующего некоторому листу — это число, которое записано в этом листе.

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

Какое минимальное количество яблок нужно удалить из дерева (точнее из некоторых его листьев), чтобы сделать дерево сбалансированным? Обратите внимание, что цель всегда можно достигнуть, удалив все яблоки.

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

В первой строке записано целое число n (2 ≤ n ≤ 105) — количество вершин в дереве. В следующей строке записаны n целых чисел a1, a2, ..., an (0 ≤ ai ≤ 108), где ai обозначает количество яблок в вершине с номером i. Гарантируется, что количество яблок в вершинах, не являющихся листьями, равно нулю.

Затем следует n - 1 строк, описывающих ребра дерева. В каждой строке записана пара целых чисел xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi) — номера вершин, соединенных ребром дерева.

Вершины дерева пронумерованы от 1 до n, а вершина с номером 1 является корнем дерева.

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

Выведите единственное целое число — минимальное количество яблок, которое нужно удалить, чтобы сбалансировать дерево.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
6
0 0 12 13 5 6
1 2
1 3
1 4
2 5
2 6
Выходные данные
6