# include <bits/stdc++.h>
using namespace std;
int n,a[1000005],cnt,root,son[1000005][2],opt[1000005];
int val[1000005],num[1000005],q;
bool flag[1000005];
string s;
stack<int>x;
void input() {
	while(cin>>s) {
		if(s=="!")a[++cnt]=-1;
		else if(s=="|")a[++cnt]=-2;
		else if(s=="&")a[++cnt]=-3;
		else {
			int sum=0;
			for(int i=0; i<s.size(); i++)
				if(s[i]>='0'&&s[i]<='9')
					sum=sum*10+s[i]-'0';
			if(s[0]=='x')a[++cnt]=sum;
			else {
				n=sum;
				return;
			}
		}
	}
}
void query() {
	for(int i=1; i<=cnt; i++) {
		opt[i]=a[i];
		if(a[i]>=1)x.push(i);
		else if(a[i]==-1) {
			int sum=x.top();
			x.pop();
			son[i][0]=sum;
			x.push(i);
		} else {
			int sum1=x.top();
			x.pop();
			int sum2=x.top();
			x.pop();
			son[i][0]=sum1;
			son[i][1]=sum2;
			x.push(i);
		}
	}
	root=x.top();
	return;
}
void dfs1(int now) {
	if(opt[now]>=1) {
		num[now]=val[opt[now]];
		return;
	} else if(opt[now]==-1) {
		dfs1(son[now][0]);
		num[now]=!num[son[now][0]];
	} else if(opt[now]==-2) {
		dfs1(son[now][0]);
		dfs1(son[now][1]);
		num[now]=num[son[now][0]]|num[son[now][1]];
	} else {
		dfs1(son[now][0]);
		dfs1(son[now][1]);
		num[now]=num[son[now][0]]&num[son[now][1]];
	}
}
void dfs2(int now) {
	if(opt[now]>=1)flag[opt[now]]=true;
	else if(opt[now]==-1)dfs2(son[now][0]);
	else if(opt[now]==-3) {
		if(num[son[now][0]]==1&&num[son[now][1]]==1) {
			dfs2(son[now][0]);
			dfs2(son[now][1]);
		} else if(num[son[now][0]]==1&&num[son[now][1]]==0)
			dfs2(son[now][1]);
		else if(num[son[now][0]]==0&&num[son[now][1]]==1)
			dfs2(son[now][0]);
		else return;
	} else {
		if(num[son[now][0]]==0&&num[son[now][1]]==0) {
			dfs2(son[now][0]);
			dfs2(son[now][1]);
		} else if(num[son[now][0]]==1&&num[son[now][1]]==0)
			dfs2(son[now][0]);
		else if(num[son[now][0]]==0&&num[son[now][1]]==1)
			dfs2(son[now][1]);
		else return;
	}
}
int main() {
	input();
	query();
	for(int i=1;i<=n;i++)scanf("%d",&val[i]);
	dfs1(root);
	dfs2(root);
	cin>>q;
	while(q--) {
		int x;
		scanf("%d",&x);
		if(flag[x])printf("%d\n",!num[root]);
		else printf("%d\n",num[root]);
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 1000005;

char s[N];
int a[N];
int son[N][2], ck;
int flag[N], c[N];
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() {
    // freopen("expr.in", "r", stdin);
    // freopen("expr.out", "w", stdout);
    gets(s);
    scanf("%d", &n);
    ck = n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    stack<int> b;
    for (int i = 0; s[i]; i += 2) {
        if (s[i] == 'x') {
            int x = 0;
            i++;
            while (s[i] != ' ') {
                x = x * 10 + s[i] - '0';
                i++;
            }
            i--;
            b.push(x);
        } else if (s[i] == '&') {
            int x = b.top();
            b.pop();
            int y = b.top();
            b.pop();
            b.push(++ck);
            a[ck] = 2;
            son[ck][0] = x;
            son[ck][1] = y;
        } else if (s[i] == '|') {
            int x = b.top();
            b.pop();
            int y = b.top();
            b.pop();
            b.push(++ck);
            a[ck] = 3;
            son[ck][0] = x;
            son[ck][1] = y;
        } else if(s[i] == '!'){
            flag[b.top()] ^= 1;
        }
    }
    int ans = dfs(ck, flag[ck]);
    dfs2(ck);
    scanf("%d", &q);
    while (q--) {
        int x;
        scanf("%d", &x);
        printf("%d\n", c[x] ? ans : !ans);
    }
    return 0;
}

好家伙，我竟无语凝噎。

思想简单，但坑点很多，看看代码吧。

给个赞吧

#include<bits/stdc++.h>
using namespace std;
string s;
int n,q,a[500010],st[100010],p=0,zhi[500010],cnt,stackk[500010][2],w[500010],c[500010];
int main(){
	getline(cin,s);
	cin>>n;
	cnt=n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=0;i<s.size();i++) {
		if(s[i]=='x') {
			i++;
			int f=0;
			while(isdigit(s[i])) {
				f=f*10+s[i]-'0';
				i++;
			} 
			st[++p]=f;
			w[f]=0;
		}
		else if(s[i]=='&') {
			w[++cnt]=1;
			stackk[cnt][1]=st[p--];
			stackk[cnt][0]=st[p--];
			a[cnt]=a[stackk[cnt][0]]&a[stackk[cnt][1]];
			st[++p]=cnt;
		}
		else if(s[i]=='|') {
			w[++cnt]=2;
			stackk[cnt][1]=st[p--];
			stackk[cnt][0]=st[p--];
			a[cnt]=a[stackk[cnt][0]]|a[stackk[cnt][1]];
			st[++p]=cnt;
		}
		else if(s[i]=='!') {
			w[++cnt]=3;
			stackk[cnt][0]=st[p--];
			a[cnt]=!a[stackk[cnt][0]];
			st[++p]=cnt;
		}
	}
	c[cnt]=1;
	for(int i=cnt;i>n;i--) {
		int l=stackk[i][0],r=stackk[i][1];
		if(w[i]==1) {
			if(((!a[l])&a[r])!=a[i])c[l]=c[i];
			if((a[l]&(!a[r]))!=a[i])c[r]=c[i]; 
		}
		else if(w[i]==2) {
			if(((!a[l])|a[r])!=a[i]) c[l]=c[i];
			if((a[l]|(!a[r]))!=a[i]) c[r]=c[i]; 
		}
		else if(w[i]==3) c[l]=c[i]; 
	}
	cin>>q;
	while(q--) {
		int k;
		cin>>k;
		printf("%d\n",a[cnt]^c[k]);
	} 
	return 0;
}