#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;

int n, m;
int w[N];
char c[N];
bool st[N];
stack<int> num ;//保存节点 编号
vector<int> g[N];//邻接表

int dfs1(int u)
{
    if (!c[u]) return w[u];
    if (c[u] == '!') w[u] = !dfs1(g[u][0]);
    else
    {
        int a = g[u][0], b = g[u][1];
        if (c[u] == '&') w[u] = dfs1(a) & dfs1(b);
        else w[u] = dfs1(a) | dfs1(b);
    }
    return w[u];
}

void dfs2(int u)
{
    st[u] = true;
    if (!c[u]) return;
    if (c[u] == '!') dfs2(g[u][0]);
    else
    {
        int a = g[u][0], b = g[u][1];
        if (c[u] == '&')
        {
            if (w[a]) dfs2(b);
            if (w[b]) dfs2(a);
        }
        else
        {
            if (!w[a]) dfs2(b);
            if (!w[b]) dfs2(a);
        }
    }
}

int main()
{
    string s;
    getline(cin, s);
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];

    m = n;
    for (int i = 0; i < s.size(); i ++ )
    {
        if (s[i] == ' ') continue;
        if (s[i] == 'x')
        {
            int j = i + 1, x = 0;
            while (j < s.size() && isdigit(s[j])) x = x * 10 + s[j ++ ] - '0';
            num.push(x);
            i = j;
        }
        else if (s[i] == '!')
        {
            c[ ++ m] = s[i];
            int la = num.top(); num.pop();
            g[m].push_back(la);
            num.push(m);
        }
        else
        {
            c[ ++ m] = s[i];
            int lb = num.top(); num.pop();
            int la = num.top(); num.pop();
            g[m].push_back(la);
            g[m].push_back(lb);
            num.push(m);
        }
    }

    int res = dfs1(m);
    dfs2(m);

    // for(int i=1; i<=n+m; i++){
    //   if(i<=n) cout << i << ":" << w[i] << " "  ;
    //   if(i>n && i<=m) cout << i << ":" << c[i] << " "  ;
    //   if(g[i].size() == 1) cout << g[i][0] << " "  ;
    //   if(g[i].size()>1) {
    //     cout << g[i][0] << " " << g[i][1] << " ";
    //   }
    //   cout << endl;
    // }

    int Q;
    cin >> Q;
    while (Q -- )
    {
        int x;
        cin >> x;
        if (st[x]) cout << (res ^ 1) << endl;
        else cout << res << endl;
    }

    return 0;
}

对于：

x1 ! x2 x4 | x3 x5 ! & & ! &
5
0 1 0 1 1
3
1
3
5

建立树的过程如下：

1:0 
2:1 
3:0 
4:| 2 3
5:& 1 4
6:1 
7:1 
8:| 6 7
9:1 
10:0 
11:& 9 10
12:| 8 11
13:| 5 12

图片如下：