CF1626E.Black and White Tree

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$.

给你一棵包含 $n$ 个顶点的树。其中部分顶点（至少两个）为黑色，其余顶点均为白色。

你将一个棋子放置在树的某个顶点上，然后执行如下操作：

• 设当前棋子所在顶点为 $x$。你选择一个黑色顶点 $y$，然后将棋子沿着从 $x$ 到 $y$ 的简单路径上的第一条边移动。

不允许在连续两次操作中选择同一个黑色顶点 $y$（即：任意两次连续操作所选的黑色顶点必须不同）。

当棋子移动到某个黑色顶点时，你结束操作（如果初始时棋子已位于黑色顶点，则不执行任何操作）；或者当已执行的操作次数超过 $100^{500}$ 时，你也结束操作。

对每个顶点 $i$，你需要判断：若棋子初始时置于顶点 $i$，是否存在一个（可能为空的）操作序列，使得棋子最终移动到某个黑色顶点。

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.

第一行包含一个整数 $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$）—— 某条边的两个端点。这些边构成一棵树。

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.

输出 $n$ 个整数。其中第 $i$ 个整数应为 $1$，当且仅当存在一个（可能为空的）操作序列，使得若棋子初始位于顶点 $i$ 上，则该序列可将其移动至某个黑色顶点；否则（即不存在这样的操作序列）该整数为 $0$。