WA on 5、6、7、10、14

#include<bits/stdc++.h>
using namespace std;
#define int long long
string s;
int len,n,x[500100],cnt,q,v;
bool need[500100];
struct dot{
	int val,opt,lson,rson,id;
	bool change;
}d[500100];//值和运算符（与或）
stack<dot>st;
void dfs(int x){
	need[x]=1;
	if(x<=n)return;
	int t1=d[d[x].lson].val,t2=d[d[x].rson].val;
	int t=d[x].opt;
	if(d[x].change)t^=1;
	if(t){
		if(t1==1&&t2==1)dfs(d[x].lson),dfs(d[x].rson);
		else if(t1==1&&t2==0)dfs(d[x].rson);
		else if(t1==0&&t2==1)dfs(d[x].lson);
	}else{
		if(t1==0&&t2==0)dfs(d[x].lson),dfs(d[x].rson);
		else if(t1==1&&t2==0)dfs(d[x].lson);
		else if(t1==0&&t2==1)dfs(d[x].rson);
	}
}
signed main(){
	getline(cin,s);len=s.size();
	cin>>n;cnt=n;
	for(int i=1;i<=n;i++){
		cin>>x[i];
		d[i]={x[i],0,0,0,i,0};
	}
	for(int i=0;i<len;i++){
		if(s[i]=='x'){
			int ct=0;++i;
			while(s[i]>='0'&&s[i]<='9'){
				ct=ct*10+s[i]-'0';
				++i;
			}
			st.push(d[ct]);
		}else{
			if(s[i]=='!'){
				dot t=st.top();st.pop();
				t.val^=1;t.change^=1;
				d[t.id].val^=1;d[t.id].change^=1;
				st.push(t);
			}else if(s[i]=='&'){
				dot t1=st.top();st.pop();
				dot t2=st.top();st.pop();
				++cnt;
				d[cnt]={t1.val&t2.val,1,t1.id,t2.id,cnt,0};
				st.push(d[cnt]);
			}else{
				dot t1=st.top();st.pop();
				dot t2=st.top();st.pop();
				++cnt;
				d[cnt]={t1.val|t2.val,0,t1.id,t2.id,cnt,0};
				st.push(d[cnt]);
			}
			++i;
		}
	}
	dfs(cnt);
	cin>>q;
	while(q--){
		cin>>v;
		if(need[v])cout<<(d[cnt].val^1)<<'\n';
		else cout<<d[cnt].val<<'\n';
	}
	return 0;
}