logo AlgoBeat OnlineJudge
登录 注册

#101450. [BZOJ 1450] SPOJ 11414. Color over a tree

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一棵有 个节点的树,每个点初始有黑白两种颜色,Seter 和 Fotile 将在这棵树上玩游戏。

他们将会轮流进行以下操作:在当前的树上选择一个白色节点 ,把 号节点和 上的所有点涂黑(包括 号点和 号点)。

当谁无法进行操作即当树上没有白色节点时,另一方就成为了胜者。

Seter 想知道,如果他是先手,那么谁是最后的胜者,如果他可以获胜,你还需要输出他第一步的所有必胜策略。

输入格式

第一行一个正整数 表示树的节点数。

第二行有 个数,其中第 个数表示第 个节点的颜色 。更具体地, 表示第 个点初始是白色的,而 表示第 个点初始是黑色的。

接下去 行,一行两个正整数 ,表示节点 和节点 之间有一条边。

输出格式

假如先手没有必胜策略,输出

否则输出若干行,每行一个正整数 ,表示先手的所有的必胜策略按升序排序后所得到的结果。

样例

样例输入 #1

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

样例输出 #1

5

样例输入 #2

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 

样例输出 #2

8
11
12

数据范围与提示

对于 的数据,,保证输入的是一棵树。