Black and White Tree
Contest: Educational Codeforces Round 121 (Rated for Div. 2)
Difficulty rating: 2400
Tags: dfs and similar, greedy, trees

You are given a tree consisting of $$$n$$$ vertices. Some of the vertices (at least two) are black, all the other vertices are white.

You place a chip on one of the vertices of the tree, and then perform the following operations:

- let the current vertex where the chip is located is $$$x$$$. You choose a black vertex $$$y$$$, and then move the chip along the first edge on the simple path from $$$x$$$ to $$$y$$$.

You are not allowed to choose the same black vertex $$$y$$$ in two operations in a row (i. e., for every two consecutive operations, the chosen black vertex should be different).

You end your operations when the chip moves to the black vertex (if it is initially placed in a black vertex, you don't perform the operations at all), or when the number of performed operations exceeds $$$100^{500}$$$.

For every vertex $$$i$$$, you have to determine if there exists a (possibly empty) sequence of operations that moves the chip to some black vertex, if the chip is initially placed on the vertex $$$i$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$) — the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 1$$$), where $$$c_i = 0$$$ means that the $$$i$$$-th vertex is white, and $$$c_i = 1$$$ means that the $$$i$$$-th vertex is black. At least two values of $$$c_i$$$ are equal to $$$1$$$.

Then $$$n-1$$$ lines follow, each of them contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — the endpoints of some edge. These edges form a tree.

Output format:
Print $$$n$$$ integers. The $$$i$$$-th integer should be equal to $$$1$$$ if there exists a (possibly empty) sequence of operations that moves the chip to some black vertex if it is placed on the vertex $$$i$$$, and $$$0$$$ if no such sequence of operations exists.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example input:
8
0 1 0 0 0 0 1 0
8 6
2 5
7 8
6 5
4 5
6 1
7 3

Example output:
0 1 1 1 1 0 1 1

Editorial:
I think there are some ways to solve this problem with casework, but let's try to come up with an intuitive and easy-to-implement approach.
It's always possible to move closer to some black vertex, no matter in which vertex you are currently and which black vertex was used in the previous operation. However, sometimes if you try to move along an edge, you immediately get forced back. Let's analyze when we can move without being forced back.
We can move along the edge $$$x \rightarrow y$$$ so that our next action is not moving back if:
• either $$$y$$$ is black (there is no next action);
• or, if we remove the edge between $$$x$$$ and $$$y$$$, the number of black vertices in $$$y$$$'s component is at least $$$2$$$ (we can use one of them to go from $$$x$$$ to $$$y$$$, and another one to continue our path).
Note that the cases $$$x \rightarrow y$$$ and $$$y \rightarrow x$$$ may be different (sometimes it will be possible to move in one direction, and impossible to move in the opposite direction).
Let's treat this possible move $$$x \rightarrow y$$$ as an arc in a directed graph. We can find all such arcs if we can answer the queries of the type "count black vertices in a subtree of some vertex", and this can be done by rooting the tree and calculating this information for each subtree with DFS.
Now, if there is a way from some vertex $$$i$$$ to some black vertex along these arcs, the answer for the vertex $$$i$$$ is $$$1$$$. How can we find all such vertices? Let's transpose the graph (change the direction of each arc to opposite), now we need to find all vertices reachable from black ones — which is easily done with multisource BFS or DFS.
The complexity of this solution is $$$O(n)$$$.