← 返回题目列表

Codeforces · 717/E

E. 漆成真的,真的深灰色

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

我看到一头粉红色的野猪,我想把它漆成黑色。黑色的野猪看起来比粉色的野猪更令人敬畏和强大。自从贾吉成为森林的统治者以来,他一直在尽力改善森林地区与附近地区的外交关系。

然而,其他一些统治者对两个地区之间的和平要求过高,因此他意识到他必须诉诸恐吓。一旦邻近地区的外交代表访问了贾吉的森林,如果他们看到一大群黑野猪,他们可能会突然改变攻击贾吉的想法。毕竟黑野猪真的很可怕。

Jaggy 的森林可以表示为一棵有 n 个顶点的树(无循环的连通图)。每个顶点代表一头野猪,颜色为黑色或粉色。贾吉派了一只松鼠穿越森林,把所有的野猪都涂成黑色。然而,松鼠经过了非常不寻常的训练,当它遍历图形时,它会改变它访问的每个顶点的颜色,无论其初始颜色如何:粉红色顶点变成黑色,黑色顶点变成粉红色。

由于贾吉太忙,无法规划松鼠的路线,他需要你的帮助。他希望你从顶点 1 开始构建一条遍历树的路径,这样最终所有顶点都是黑色的。步行是一系列顶点,因此树中每个连续的对之间都有一条边。

输入

输入的第一行包含整数 n (2 ≤ n ≤ 200 000),表示树中的顶点数。接下来的n行包含n个整数,代表节点的颜色。

如果第 i 个整数为 1,则第 i 个顶点为黑色,如果第 i 个顶点为粉色,则为 - 1。

接下来的 n - 1 行中的每一行都包含两个整数,它们表示由边连接的顶点的索引。顶点编号从 1 开始。

输出

松鼠的输出路径:按照访问的顺序输出访问过的节点的索引序列。如果所有节点最初都是黑色的,则应打印 1。解决方案保证存在。如果问题有多个解,您可以输出其中任何一个,只要序列长度不超过 107。

示例

输入 #1

5
1
1
-1
1
-1
2 5
4 3
2 4
4 1

输出 #1

1 4 2 5 2 4 3 4 1 4 1

注意

一开始,松鼠位于节点 1,其颜色为黑色。接下来的步骤如下:

- 从节点 1 我们走到节点 4 并将其颜色更改为粉红色。
- 从节点 4 走到节点 2 并将其颜色更改为粉红色。
- 从节点 2 走到节点 5,并将其颜色更改为黑色。
- 从节点 5 我们返回到节点 2 并将其颜色更改为黑色。
- 从节点 2 走到节点 4,并将其颜色更改为黑色。
- 我们访问节点 3 并将其颜色更改为黑色。
- 我们访问节点 4 并将其颜色更改为粉红色。
- 我们访问节点 1 并将其颜色更改为粉红色。
- 我们访问节点 4 并将其颜色更改为黑色。
- 我们访问节点 1 并将其颜色更改为黑色。