C. Путь наибольшего веса

В вершинах дерева написаны целые числа, возможно отрицательные. Найдите наибольшую сумму чисел на простом пути. Путь не может быть пустым: он содержит хотя бы одну вершину.

Это та же схема, что в задаче про диаметр, но с двумя поворотами.

В первой строке - число $n$ ($1 \le n \le 10^5$).

Во второй строке - $n$ чисел $a_i$ ($|a_i| \le 10^9$).

В следующих $n - 1$ строках - пары $u$, $v$ - рёбра дерева.

Одно число - наибольшая сумма чисел на простом пути.