发现本题为公平组合游戏，因此考虑用 \(\text{SG}\) 函数来解决。
设 \(\text{SG}(x)\) 为以 \(x\) 为根的子树的 \(\text{SG}\) 值。对于点 \(x\)，可以枚举其子树内的每一个白点，删去该点到 \(x\) 的所有点，然后以 \(x\) 为根的子树会分裂为一个森林，也就是 \(x\) 状态可以转移到这个森林的状态，一个森林的 \(\text{SG}\) 值为每棵树的 \(\text{SG}\) 值异或和。\(\text{SG}(x)\) 即为子树内所有白点删去后形成的森林对应的 \(\text{SG}\) 值取 \(\text{mex}\)。
考虑用数据结构来优化这个过程，每个节点上都用一个 \(01\ Trie\) 来维护其子树内所有白点删去后对应的森林的 \(\text{SG}\) 值。设 \(y\) 为 \(x\) 的一个儿子，那么 \(y\) 对应的 \(01\ Trie\) 中维护的信息还需再异或上 \(x\) 其他儿子的 \(\text{SG}\) 值的异或和才是其正确的信息。整体异或一个值可以用打标记，交换左右儿子来实现。加上 \(y\) 的贡献即为将 \(y\) 对应的 \(01\ Trie\) 合并到 \(x\) 上。
最后再 \(dfs\) 一遍，若一个点的后继状态为必败状态，则该点可以作为第一步选的点。
#include<bits/stdc++.h>
#define maxn 200010
#define maxm 4000010
using namespace std;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,tot,cnt;
int c[maxn],sg[maxn],ans[maxn],rt[maxn],ch[maxm][2],tag[maxm];
bool cov[maxm];
struct edge
{
int to,nxt;
}e[maxn];
int head[maxn],edge_cnt;
void add(int from,int to)
{
e[++edge_cnt]={to,head[from]},head[from]=edge_cnt;
}
void pushtag(int p,int k,int x)
{
if(k==-1) return;
if(x>>k&1) swap(ch[p][0],ch[p][1]);
tag[p]^=x;
}
void pushdown(int p,int k)
{
if(!tag[p]) return;
pushtag(ch[p][0],k-1,tag[p]),pushtag(ch[p][1],k-1,tag[p]),tag[p]=0;
}
void insert(int &p,int k,int x)
{
if(!p) p=++tot;
if(k==-1)
{
cov[p]=true;
return;
}
insert(ch[p][x>>k&1],k-1,x);
cov[p]=cov[ch[p][0]]&cov[ch[p][1]];
}
int merge(int x,int y,int k)
{
if(!x||!y) return x+y;
if(k==-1)
{
cov[x]|=cov[y];
return x;
}
pushdown(x,k),pushdown(y,k);
ch[x][0]=merge(ch[x][0],ch[y][0],k-1);
ch[x][1]=merge(ch[x][1],ch[y][1],k-1);
cov[x]=cov[ch[x][0]]&cov[ch[x][1]];
return x;
}
int mex(int p,int k)
{
if(!p||k==-1) return 0;
pushdown(p,k);
if(cov[ch[p][0]]) return (1<<k)|mex(ch[p][1],k-1);
return mex(ch[p][0],k-1);
}
void dfs_get(int x,int fa)
{
int v=0;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==fa) continue;
dfs_get(y,x),v^=sg[y];
}
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==fa) continue;
pushtag(rt[y],20,v^sg[y]);
rt[x]=merge(rt[x],rt[y],20);
}
if(!c[x]) insert(rt[x],20,v);
sg[x]=mex(rt[x],20);
}
void dfs_ans(int x,int fa,int v)
{
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==fa) continue;
v^=sg[y];
}
if(!v&&!c[x]) ans[++cnt]=x;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==fa) continue;
dfs_ans(y,x,v^sg[y]);
}
}
int main()
{
read(n);
for(int i=1;i<=n;++i) read(c[i]);
for(int i=1;i<n;++i)
{
int x,y;
read(x),read(y);
add(x,y),add(y,x);
}
dfs_get(1,0);
if(!sg[1]) puts("-1");
else
{
dfs_ans(1,0,0),sort(ans+1,ans+cnt+1);
for(int i=1;i<=cnt;++i) printf("%d ",ans[i]);
}
return 0;
}