COT3 - Combat on a tree

题意翻译

## 题面描述 Alice和Bob在一棵$n$个节点的树上玩游戏。每个节点最初都是黑色或白色。 他们轮流执行以下操作: 从当前树中选择一个白色节点$v$,将路径$(1,v)$上的所有白色节点都变为黑色.最后操作的玩家获胜.爱丽丝先手。当他们都使用最佳策略时,求是否能够必胜,并求出第一步的方案. ## 输入格式: 第一行输入包含一个整数$n$,表示树中节点的数量.$1 \le N \le 10^5$ 第二行包含n个整数$c_1,c_2,\dots c_n$.$ 0 \le c_i \le 1$, $c_i = 0$表示第$i$个节点初始为白色,$c_i = 1$表示黑色。 接下来$n-1$行每行包含两个整数$u$和$v$,表示树上的边$(u,v)$. ## 输出格式 如果无法取胜输出$-1$. 否则输出Alice第一步所有可选的节点. 感谢@The_Unbeatable 提供的翻译

题目描述

Alice and Bob are playing a game on a tree of n nodes.Each node is either black or white initially. They take turns to do the following operation: Choose a white node v from the current tree; Color all white nodes on Path(1,v) to black. The player who takes the last turn wins. Now Alice takes the first turn.Help her find out if she can win when they both use optimal strategy.

输入输出格式

输入格式


The first line of input contains a integer n representing the number of nodes in the tree. 1<=n<=100000 The second line contains n intergers c1,c2,..cn.0<=ci<=1. ci=0 means the ith node is white initially and ci=1 means black. Next n-1 lines describes n-1 edges in the tree.Each line contains two integers u and v,means there is a edge connecting u and v.

输出格式


If Alice can't win print -1. Otherwise determine all the nodes she can choose in the first turn in order to win.Print them in ascending order.

输入输出样例

输入样例 #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