#451. 1450. SPOJ 11414. Color over a tree

1450. SPOJ 11414. Color over a tree

#1450. SPOJ 11414. Color over a tree

题目描述

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 

数据范围与提示