SPOJ-COT3

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define int long long
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

const int MXN = 5e6;

int su[MXN], le[MXN], ri[MXN], lz[MXN], de[MXN];
int nx = 1;
vector<int> vls[MXN];

int create_node(int d = 17) {
    de[nx] = d; nx += 1;
    assert(nx < MXN);
    return nx-1;
}
void xor_all(int i, int v) {
    lz[i] ^= v;
}
void push_node(int i) {
    if (!de[i]) return;
    if ((1ll<<(de[i]-1)) & lz[i]) {
        swap(le[i], ri[i]);
    }
    if (le[i]) lz[le[i]] ^= lz[i];
    if (ri[i]) lz[ri[i]] ^= lz[i];
    lz[i] = 0;
}
void pull_node(int i) {
    if (!de[i]) return;
    push_node(i);
    su[i] = su[le[i]] + su[ri[i]];
}
int insert_value(int v, int ci, int cl = 0, int cr = (1ll<<17)-1) {
    pull_node(ci);
    if (v == cl && v == cr) {
        if (su[ci]) return 0;
        su[ci] = 1;
        return 1;
    } else {
        int cm = (cl+cr)/2;
        int res = 0;
        if (v <= cm) {
            if (!le[ci]) le[ci] = create_node(de[ci]-1);
            res = insert_value(v, le[ci], cl, cm);
        } else {
            if (!ri[ci]) ri[ci] = create_node(de[ci]-1);
            res = insert_value(v, ri[ci], cm+1, cr);
        }
        pull_node(ci);
        return res;
    }
}
void add_value(int ci, int v) {
    if (insert_value(v,ci)) {
        vls[ci].push_back(v);
    }
}
int get_mex(int ci) {
    if (!de[ci]) return su[ci];
    int nc = (1ll<<de[ci]);
    pull_node(ci);
    if (su[ci] == nc) return nc;
    int lmx = get_mex(le[ci]);
    if (lmx == nc/2) {
        return nc/2+get_mex(ri[ci]);
    }
    return lmx;
}
int merge(int a, int b) {
    if (!a) return b;
    if (!b) return a;
    pull_node(a);
    pull_node(b);
    le[a] = merge(le[a], le[b]);
    ri[a] = merge(ri[a], ri[b]);
    pull_node(a);
    return a;
}

int n, c[MXN], rt[MXN], sg[MXN], ans[MXN];
vector<int> adj[MXN];

void dfs(int v, int p) {
    if (find(all(adj[v]),p) != end(adj[v])) {
        adj[v].erase(find(all(adj[v]),p));
    }
    rt[v] = create_node();
    int txor = 0; //total xor
    for (int u : adj[v]) {
        assert(u != p);
        dfs(u, v);
        txor ^= sg[u];
    }
//  cout << v+1 << ": " << txor << "\n";
    for (int u : adj[v]) {
        xor_all(rt[u], txor^sg[u]);
        rt[v] = merge(rt[v], rt[u]);
    }

    if (!c[v]) {
        insert_value(txor, rt[v]);
    }
    sg[v] = get_mex(rt[v]);
}

void dfs2(int v, int p) {
    int txor = 0;
    for (int i : adj[v]) {
        txor ^= sg[i];
    }
    ans[v] = sg[v]^ans[p]^txor;
    for (int i : adj[v]) {
        dfs2(i, v);
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; i++) cin >> c[i];
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v; --u; --v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    dfs(0,0);
/*  cout << "\n\n";
    for (int i = 0; i < n; i++) {
        cout << i+1 << ": " << sg[i] << "\n";
    }
    cout << "\n\n";*/
    ans[0] = sg[0];
    dfs2(0,0);
    if (!sg[0]) cout << -1 << "\n";
    for (int i = 0; i < n; i++) {
        if (!c[i] && !ans[i]) cout << i+1 << "\n";
    }

    return 0;
}