SPOJ 11414. Color over a tree

内存限制：128 MiB 时间限制：10 Sec

提交提交记录讨论

Seter和Fotile在一棵N个点的树上玩游戏。这棵树的每个点不是黑色的就是白色的。

他们轮流进行以下操作：

在当前的树上选择一个白色节点；

把1号点到选择节点的路径上所有点涂黑。

Seter或Fotile输掉游戏当且仅当无法操作（没有白色节点）。

Seter用石头剪刀布获得了先手机会，但是他知道Fotile很聪明，会按照最优策略选点

他想知道自己有没有可能赢得游戏，否则他就要掀桌了。

第一行包含一个正整数N表示树的节点数。 1<=n<=100000

第二行包括N个0或1：c1,c2,..cn。

ci=0 表示第i个点一开始是白色的而 ci=1 表示黑色。

接下来N-1行每行两个整数u,v描述整棵树。

如果Seter输定了或者你也不会做，输出-1让他掀桌.

否则按照增序输出所有Seter第一步可以选择的点，使得Seter能获胜。

样例输入


			Input#1:

8

1 1 0 1 0 0 1 0

1 2

1 3

2 6

3 4

3 5

5 7

7 8 

Input#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

样例输出


			Output#1:

5



Output#2

8

11

12

#1450. SPOJ 11414. Color over a tree

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示