← 返回题目列表

Codeforces · 1626/E

E. 黑白树

中文机器翻译题面 查看原题

给你一棵由 $$$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$$$ 上),则第 $$$i$$$ 个整数应等于 $$$1$$$;如果不存在这样的操作序列,则第 $$$0$$$ 整数应等于 $$$0$$$。

示例

输入 #1

8
0 1 0 0 0 0 1 0
8 6
2 5
7 8
6 5
4 5
6 1
7 3

输出 #1

0 1 1 1 1 0 1 1