bzoj#P1450. SPOJ 11414. Color over a tree
SPOJ 11414. Color over a tree
题目描述
有一棵有 个节点的树,每个点初始有黑白两种颜色,Seter 和 Fotile 将在这棵树上玩游戏。
他们将会轮流进行以下操作:在当前的树上选择一个白色节点 ,把 号节点和 上的所有点涂黑(包括 号点和 号点)。
当谁无法进行操作即当树上没有白色节点时,另一方就成为了胜者。
Seter 想知道,如果他是先手,那么谁是最后的胜者,如果他可以获胜,你还需要输出他第一步的所有必胜策略。
输入格式
第一行一个正整数 表示树的节点数。
第二行有 个数,其中第 个数表示第 个节点的颜色 。更具体地, 表示第 个点初始是白色的,而 表示第 个点初始是黑色的。
接下去 行,一行两个正整数 ,表示节点 和节点 之间有一条边。
输出格式
假如先手没有必胜策略,输出 。
否则输出若干行,每行一个正整数 ,表示先手的所有的必胜策略按升序排序后所得到的结果。
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
数据规模与约定
对于 的数据,,,保证输入的是一棵树。