给你一棵由 $$$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