bzoj#P1450. SPOJ 11414. Color over a tree

SPOJ 11414. Color over a tree

题目描述

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

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

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

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

输入格式

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

第二行有 nn 个数,其中第 ii 个数表示第 ii 个节点的颜色 cic_i。更具体地,ci=0c_i=0 表示第 ii 个点初始是白色的,而 ci=1c_i=1 表示第 ii 个点初始是黑色的。

接下去 n1n-1 行,一行两个正整数 x,yx,y,表示节点 xx 和节点 yy 之间有一条边。

输出格式

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

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

8
1 1 0 1 0 0 1 0
1 2
1 3
2 6
3 4
3 5
5 7
7 8 
5
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

数据规模与约定

对于 100%100\% 的数据,1n1051\le n\le10^5ci{0,1}c_i\in\{0,1\},保证输入的是一棵树。