E. Черно-белое дерево
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$n$$$ вершин. Некоторые вершины дерева (хотя бы две) — черные, остальные — белые.

Вы ставите фишку в какую-то из вершин дерева и после этого проводите следующие операции:

  • пусть фишка сейчас находится в вершине $$$x$$$. Вы выбираете черную вершину $$$y$$$, а затем перемещаете фишку по первому ребру в простом пути из $$$x$$$ в $$$y$$$.

Вы не можете выбирать одну и ту же вершину $$$y$$$ в двух операциях подряд (то есть для любых двух последовательных операций выбранные черные вершины должны быть различны).

Вы заканчиваете операции, когда фишка оказывается в черной вершине (если она изначально в черной вершине — вы не выполняете операции вообще), или когда количество выполненных операций становится больше $$$100^{500}$$$.

Для каждой вершины $$$i$$$ вы должны определить, существует ли (не обязательно непустая) последовательность операций, в результате которой фишка окажется в черной вершине, если изначально фишка расположена в вершине $$$i$$$.

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

В первой строке задано одно целое число $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$) — количество вершин дерева.

Во второй строке заданы $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 1$$$), где $$$c_i = 0$$$ означает, что $$$i$$$-я вершина — белая, а $$$c_i = 1$$$ означает, что $$$i$$$-я вершина — черная. Хотя бы два значения $$$c_i$$$ равны $$$1$$$.

Затем следует $$$n-1$$$ строка, каждая из которых содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — концы некоторого ребра. Эти ребра задают дерево.

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

Выведите $$$n$$$ целых чисел. $$$i$$$-е из них должно быть равно $$$1$$$, если существует (возможно, пустая) последовательность операций, которая перемещает фишку в черную вершину, если изначально расположить ее в вершине $$$i$$$, или $$$0$$$, если такой последовательности операций не существует.

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