染色游戏

题目描述

$Alice$ 和 $Bob$ 在一棵有根树上玩一个游戏。初始状态下这棵树的每个结点被染成了黑色或者白色。

游戏时两人反复轮流进行以下操作：选一个目前仍然为白色的结点，将这个点以及它到根的路径上的所有点都染为黑色。当前的操作结束后整棵树都变黑的一方胜利。

先手的 $Alice$ 想知道自己是否存在必胜策略，如果是，她进而希望知道在确保胜利的前提下第一步可以采取的行动。

第一行有一个整数 $n$ ，表示这棵树的结点个数。结点从 $1$ 开始编号至 $n$ 结束， $1$ 号点为根。

第二行有 $n$ 个整数 $c_{1}$ ， $c_{2}$ ， $\ldots$ ， $c_{n}$ ，表示 $n$ 个点在初始状态下的颜色。 $c_{i} = 0$ 表示 $i$ 号点一开始是白色的，否则 $c_{i} = 1$ ， $i$ 号点在初始状态下为黑色。

接下来的 $n-1$ 行，每行包含两个整数 $u$ ， $v$ ，表示树中存在一条连接着 $u$ 号结点与 $v$ 号结点的边。

如果 $Alice$ 没有必胜策略，输出 $-1$ 。

否则升序输出所有 $Alice$ 第一步能够选择的结点的编号，使得在该操作后 $Alice$ 仍然存在必胜策略。每行一个整数。

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

20
1 1 1 0 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0
1 2
2 3
2 4
1 5
1 6
5 7
5 8
2 9
8 10
1 11
1 12
9 13
6 14
14 15
7 16
11 17
2 18
7 19
12 20

8
11
12