davidwang's Blog

我才不会说是被题目吸引进来的

然后就吓傻了，我还以为是那种朴素的森林取子问题，节点sg就是字节点抑或+1然后错的酸爽，然后赶紧问

原来并没有什么结论因为一些点已经被放了

然后就只能暴力计算sg的值，可以使用Trie树搞一搞，然后膜了一下huzecong的题解

……

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 100010,Log=17;
struct node{
	int lch,rch,d,flag;
}s[N*Log*2];
#define l(x) s[x].lch
#define r(x) s[x].rch
int root[N],sg[N],vis[N],sum[N],up[N],fa[N],n,a[N],cnt,tot,ans[N];
vector<int>g[N];
inline int reverse(int x){
	int ret=0;
	for (int i=1;i<=Log;i++)
		if (x>>i-1&1) ret+=1<<Log-i;
	return ret;
}
inline void push_up(int x){
	s[x].flag=s[l(x)].flag && s[r(x)].flag;
}
inline void push_down(int x){
	if (s[x].d){
		if (l(x)) s[l(x)].d^=s[x].d>>1;
		if (r(x)) s[r(x)].d^=s[x].d>>1;
		if (s[x].d&1) swap(l(x),r(x));
		s[x].d=0;
	}
}
inline int getans(int x){
	int ret=0;
	for (int i=Log;x;i--){
		push_down(x);
		if (s[l(x)].flag){
			ret+=1<<i-1;
			x=r(x);
		}else x=l(x);
	}
	return ret;
}
inline void insert(int x,int num,int d){
	push_down(x);
	if (num>>d-1&1){
		if (r(x)==0) r(x)=++cnt;
		if (d!=1) insert(r(x),num,d-1);
		else s[r(x)].flag=1;
	}else{
		if (l(x)==0) l(x)=++cnt;
		if (d!=1) insert(l(x),num,d-1);
		else s[l(x)].flag=1;
	}
	push_up(x);
}
int merge(int l,int r){
	if (l==0 || s[r].flag) return r;
	if (r==0 || s[l].flag) return l;
	push_down(r); push_down(l);
	int now = ++cnt;
	l(now)=merge(l(l),l(r));
	r(now)=merge(r(l),r(r));
	push_up(now);
	return now;
}
inline void init()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1;i<n;i++){
		int x=read(),y=read();
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i=1;i<=n;i++){
		root[i]=++cnt;
	}
}
inline void dfs(int x){
	for (vector<int>::iterator it=g[x].begin();it!=g[x].end();it++){
		if (*it==fa[x]) continue;
		fa[*it]=x;
		dfs(*it);
		sum[x]^=sg[*it];
	}
	for (vector<int>::iterator it=g[x].begin();it!=g[x].end();it++){
		if (*it==fa[x]) continue;
		s[root[*it]].d^=reverse(sg[*it]^sum[x]);
		root[x]=merge(root[x],root[*it]);
	}
	if (a[x]==0) insert(root[x],sum[x],Log);
	sg[x]=getans(root[x]);
}
inline void calc(int x){
	if ((up[x]^sum[x])==0 && a[x]==0) ans[++tot]=x;
	for (vector<int>::iterator it=g[x].begin();it!=g[x].end();it++){
		if (*it==fa[x]) continue;
		up[*it]=up[x]^sum[x]^sg[*it];
		calc(*it);
	}
	return;
}
inline void print()
{
	if (tot==0){ puts("-1"); return ;}
	sort(ans+1,ans+tot+1);
	for (int i=1;i<=tot;i++){
		printf("%d\n",ans[i]);
	}
}
int main()
{
	init();
	dfs(1);
//	for (int i=1;i<=n;i++) printf("%d\n",sg[i]);
	calc(1);
	print();
	return 0;
}