本题代码

#include<bits/stdc++.h> 
using namespace std;
const int N=1e5+7,L=1e6+7;
struct Node{
	int fa,chd[2],v,ng,u;
	char op;
	int V(){ return ng? !v : v;}
}tr[N<<1];
char s[L];
int n,c,stk[N<<1],tp;
void init(){
	for(int i=0;s[i];++i){
		if(s[i]==' ') continue;
		if(s[i]=='x') {
			int j=i+1,id=0;
			while(s[j]>='0'&&s[j]<='9')
				id=id*10+s[j++]-'0';
			stk[++tp]=id,i=j;
			continue;
		}
		if(s[i]=='!'){tr[stk[tp]].ng^=1;continue;}
		tr[++c].op=s[i];
		int rc=stk[tp--],lc=stk[tp--];
		tr[lc].fa=tr[rc].fa=c,tr[c].chd[1]=rc,tr[c].chd[0]=lc;
		if(s[i]=='&') {
			tr[c].v=tr[lc].V()&tr[rc].V();
			if(tr[c].v==0)
				tr[lc].u|=(tr[rc].V()==0),tr[rc].u|=(tr[lc].V()==0);
		}
		else {
			tr[c].v=tr[lc].V()|tr[rc].V();
			if(tr[c].v==1)
				tr[lc].u|=(tr[rc].V()==1),tr[rc].u|=(tr[lc].V()==1);
		}
		stk[++tp]=c;
	}
}
void lable(int x){
	int lc=tr[x].chd[0],rc=tr[x].chd[1];
	if(lc==0) return;
	tr[lc].u|=tr[x].u,tr[rc].u|=tr[x].u;
	lable(lc),lable(rc);
}
int main() {
	freopen("expr.in","r",stdin);
	freopen("expr.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.getline(s,L);
	cin>>n;
	for(int i=1;i<=n;++i) cin>>tr[i].v;
	c=n;init();lable(c);//c为根节点
	int q;
	cin>>q;
	while(q--)
	{
		int x;
		cin>>x;
		cout<<(tr[x].u?tr[c].V():!tr[c].V())<<endl;
	}
    return 0;
}