G. Сумма префиксных сумм
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим сумму префиксных сумм массива $$$[s_1, s_2, \dots, s_k]$$$ как $$$s_1 + (s_1 + s_2) + (s_1 + s_2 + s_3) + \dots + (s_1 + s_2 + \dots + s_k)$$$.

Вам задано дерево, состоящее из $$$n$$$ вершин. В каждой вершине $$$i$$$ записано целое число $$$a_i$$$. Определим значение простого пути от вершины $$$u$$$ до вершины $$$v$$$ следующим образом: рассмотрим все вершины на пути от $$$u$$$ до $$$v$$$, выпишем числа, записанные на этих вершинах, в порядке их появления на пути, и вычислим сумму префиксных сумм получившейся последовательности.

Ваша задача — найти максимальное значение по всем путям в дереве.

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

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 150000$$$) — число вершин в дереве.

Затем следует $$$n - 1$$$ строк, описывающих ребра дерева. Каждая строка содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$), обозначающие ребро между вершинами $$$u_i$$$ и $$$v_i$$$. Гарантируется, что эти ребра образуют дерево.

Последняя строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^6$$$).

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

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

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

Ответ в первом примере достигается, если выбрать путь из вершины $$$3$$$ в вершину $$$1$$$. Мы получаем последовательность $$$[3, 3, 7, 1]$$$, сумма префиксных сумм которой равна $$$36$$$.