二周目，大彻大悟

#include <iostream>
#include <stack>
#include <sstream>
using namespace std;

const int N = 1e6+10;
int n, qq, opidx;
int a[N], q[N], l[N], r[N], vip[N];
char op[N];

int dfs1(int u){
    if(u <= n) return a[u];
    if(op[u] == '!') a[u] = !dfs1(r[u]);
    else if(op[u] == '&') a[u] = dfs1(l[u]) & dfs1(r[u]);
    else if(op[u] == '|') a[u] = dfs1(l[u]) | dfs1(r[u]);
    return a[u];
}

void dfs2(int u){
    vip[u] = 1;
    if(u <= n) return;
    if(op[u] == '&'){
        if(a[l[u]]) dfs2(r[u]);
        if(a[r[u]]) dfs2(l[u]);
    }else if(op[u] == '|'){
        if(!a[l[u]]) dfs2(r[u]);
        if(!a[r[u]]) dfs2(l[u]);
    }else if(op[u] == '!'){
        dfs2(r[u]);
    }
}

int main(){
    string str, s;
    stack<int> num;
    getline(cin, str);
    cin >> n;
    for (int i = 1; i <= n; i ++ )cin >> a[i];
    opidx = n+1;
    cin >> qq;
    for (int i = 1; i <= qq; i ++ )cin >> q[i];
    stringstream ssin(str);
    //建树
    while (ssin >> s){
        if(s[0] == 'x'){
            int tmp = stoi(s.substr(1));
            num.push(tmp);
        }else{
            op[opidx] = s[0];
            r[opidx] = num.top();
            num.pop();
            if(s[0] == '!') num.push(opidx++);
            else{
                l[opidx] = num.top();
                num.pop();
                num.push(opidx++);
            }
        }
    }
    int root = num.top();
    int ans = dfs1(root);
    dfs2(root);

    for (int i = 1; i <= qq; i ++ ){
        if(vip[q[i]]) cout << !ans << endl;
        else cout << ans << endl;
    }
    return 0;
}