[CSP-J2020] 表达式

#include <bits/stdc++.h>
using namespace std;
string s;
stack<int> sta;
int a[1000005];
int son[1000005][2], tot;
int flag[1000005], c[1000005];
int n, q;
int dfs(int u, int g)
{
    a[u] ^= g;
    if (u <= n)
    {
        return a[u];
    }
    int x = dfs(son[u][0], g ^ flag[son[u][0]]);
    int y = dfs(son[u][1], g ^ flag[son[u][1]]);
    if (a[u] == 2)
    {
        if (x == 0)
            c[son[u][1]] = 1;
        if (y == 0)
            c[son[u][0]] = 1;
        return x & y;
    }
    else
    {
        if (x == 1)
            c[son[u][1]] = 1;
        if (y == 1)
            c[son[u][0]] = 1;
        return x | y;
    }
}
void dfs2(int u)
{
    if (u <= n)
        return;
    c[son[u][0]] |= c[u];
    c[son[u][1]] |= c[u];
    dfs2(son[u][0]);
    dfs2(son[u][1]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    getline(cin, s);
    cin >> n;
    tot = n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 0; i < s.length(); i += 2)
    {
        if (s[i] == 'x')
        {
            int x = 0;
            i++;
            while (s[i] != ' ')
            {
                x = x * 10 + s[i] - '0';
                i++;
            }
            i--;
            sta.push(x);
        }
        else if (s[i] == '&')
        {
            int x = sta.top();
            sta.pop();
            int y = sta.top();
            sta.pop();
            sta.push(++tot);
            a[tot] = 2;
            son[tot][0] = x;
            son[tot][1] = y;
        }
        else if (s[i] == '|')
        {
            int x = sta.top();
            sta.pop();
            int y = sta.top();
            sta.pop();
            sta.push(++tot);
            a[tot] = 3;
            son[tot][0] = x;
            son[tot][1] = y;
        }
        else if (s[i] == '!')
        {
            flag[sta.top()] ^= 1;
        }
    }
    int ans = dfs(tot, flag[tot]);
    dfs2(tot);
    cin >> q;
    while (q--)
    {
        int x;
        cin >> x;
        if (c[x])
            cout << ans << "\n";
        else
            cout << !ans << "\n";
    }
    return 0;
}