F. Вышки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$. Для вершины с номером $$$i$$$ известна её высота $$$h_i$$$. Вы можете установить любое количество вышек в вершины, для каждой вышки вы можете выбрать, в какую вершину её поставить, а также выбрать её эффективность. Установка вышки с эффективностью $$$e$$$ стоит $$$e$$$ монет, где $$$e > 0$$$.

Считается, что в вершине $$$x$$$ ловит связь, если для какой-то пары вышек в вершинах $$$u$$$ и $$$v$$$ ($$$u \neq v$$$, но может быть, что $$$x = u$$$ или $$$x = v$$$) с эффективностями соответственно $$$e_u$$$ и $$$e_v$$$ выполняется, что $$$\min(e_u, e_v) \geq h_x$$$ и $$$x$$$ лежит на пути между $$$u$$$ и $$$v$$$.

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

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

В первой строке вводится целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество вершин в дереве.

Во второй строке вводятся $$$n$$$ целых чисел $$$h_i$$$ ($$$1 \le h_i \le 10^9$$$) — высоты вершин.

В следующих $$$n - 1$$$ строках вводятся пары чисел $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — ребра в дереве. Гарантируется, что данные ребра образуют дерево.

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

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

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

В первом тесте оптимально установить две вышки с эффективностью $$$2$$$ в $$$1$$$ и $$$3$$$ вершины.

Во втором тесте оптимально установить вышку с эффективностью $$$1$$$ в вершину $$$1$$$ и две вышки с эффективностью $$$3$$$ во $$$2$$$ и $$$5$$$ вершины.

В третьем тесте оптимально установить две вышки с эффективностью $$$6$$$ в $$$1$$$ и $$$2$$$ вершины.