Самый ценный путь

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

В первой строке $n$ ($1 \le n \le 2 \cdot 10^5$). Во второй — веса $w_1, \ldots, w_n$ ($|w_i| \le 10^9$). В следующих $n - 1$ строках — рёбра дерева.

Выведите наибольший суммарный вес пути.