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

Вам задано дерево, состоящее из $$$n$$$ вершин. Деревом называется связный неориентированный граф с $$$n-1$$$ ребром. Каждая вершина $$$v$$$ этого дерева имеет свой цвет ($$$a_v = 1$$$, если вершина $$$v$$$ белая, и $$$0$$$, если вершина $$$v$$$ черная).

Вам нужно решить следующую задачу для каждой вершины $$$v$$$: какую максимальную разницу между количеством белых вершин и количеством черных вершин вы можете получить, если выберете некоторое поддерево заданного дерева, которое содержит вершину $$$v$$$? Поддеревом дерева называется связный подграф заданного дерева. Более формально, если вы выберете поддерево, которое содержит $$$cnt_w$$$ белых вершин и $$$cnt_b$$$ черных вершин, вам нужно максимизировать $$$cnt_w - cnt_b$$$.

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

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

Вторая строка теста содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$), где $$$a_i$$$ — это цвет $$$i$$$-й вершины.

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

Гарантируется, что заданные ребра образуют дерево.

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

Выведите $$$n$$$ целых чисел $$$res_1, res_2, \dots, res_n$$$, где $$$res_i$$$ — максимальная возможная разница между количеством белых и количеством черных вершин в некотором поддереве, которое содержит вершину $$$i$$$.

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

Первый тестовый пример представлен ниже:

Черные вершины выделены жирным.

Во втором тестовом примере лучшими поддеревьями для вершин $$$2, 3$$$ и $$$4$$$ являются вершины $$$2, 3$$$ и $$$4$$$ соответственно. И лучшим поддеревом для вершины $$$1$$$ является поддерево, состоящее из вершин $$$1$$$ и $$$3$$$.