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

Недавно Максим прилетел в Корею и захотел попасть на фестиваль фейерверков в Пусане.

Система поездов Кореи представляет собой дерево из $$$n$$$ вершин. Пути поездов двусторонние, и для каждой поездки нужно потратить $$$1$$$ билет.

Максим начинает свой путь из вершины $$$1$$$ и должен попасть в вершину $$$n$$$. Находясь в вершине $$$i$$$ можно купить любое количество билетов по $$$a_i$$$ вон.

Найдите минимальное количество вон, необходимое, чтобы Максим попал в вершину $$$n$$$ из вершины $$$1$$$.

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

В первой строке дано число $$$n$$$ $$$(2 \leq n \leq 2\cdot 10^{5})$$$ — количество вершин в дереве.

Во второй строке даны $$$n$$$ чисел — массив $$$a$$$ $$$(1 \leq a_i \leq 10^6)$$$. $$$a_i$$$ — цена одного билета в вершине $$$i$$$.

В следующих $$$n-1$$$ строках дано по $$$2$$$ числа: $$$v_i, u_i$$$ — концы путей поездов.

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

Выведите минимальное количество денег, необходимое, чтобы Максим попал в вершину $$$n$$$ из вершины $$$1$$$.

Примеры
Входные данные
6
100 10 5 4 100 10
1 2
2 3
3 4
1 5
5 6
Выходные данные
130
Входные данные
7
8 1 5 7 9 4 3
1 2
1 3
2 4
3 5
1 6
2 7
Выходные данные
9
Входные данные
9
1000 100 30 100 10 1000 1000 1000 10
1 2
2 3
2 4
4 5
1 6
6 7
7 8
8 9
Выходные данные
1260