55求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
int n,q,top,m,idx;
int w[1000005],stk[1000005],h[1000005],ne[1000005],e[1000005];
bool vis[1000005];
char op[1000005];
void add(int a,int b)
{
	e[++idx]=b;
	ne[idx]=h[a];
	h[a]=idx;
}
int dfs1(int u)
{
	if(u<=n)
	{
		return w[u];
	}
	if(op[u]=='!')
	{
		return w[u]=!dfs1(e[h[u]]);
	}
	if(op[u]=='&')
	{
		w[u]=1;
		for(int i=h[u];i;i=ne[i])
		{
			w[u]&=dfs1(e[i]);
		}
		return w[u];
	}
	if(op[u]=='|')
	{
		w[u]=0;
		for(int i=h[u];i;i=ne[i])
		{
			w[u]|=dfs1(e[i]);
		}
		return w[u];
	}
}
void dfs2(int u)
{
	vis[u]=1;
	if(u<=n)
	{
		return;
	}
	if(op[u]=='!')
	{
		return dfs2(e[h[u]]);
	}
	else
	{
		int a=e[h[u]],b=e[ne[h[u]]];
		if(op[u]=='&')
		{
			if(w[a])
			{
				return dfs2(b);
			}
			if(w[b])
			{
				return dfs2(a);
			}
		}
		else if(op[u]=='|')
		{
			if(!w[a])
			{
				return dfs2(b);
			}
			if(!w[b])
			{
				return dfs2(a);
			}
		}
	}
}
signed main()
{
	//freopen("string.in", "r", stdin);
	//freopen("string.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	getline(cin,s);
	cin>>n;
	m=n;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i];
	}
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='x')
		{
			i++;
			int num=0;
			while(s[i]>='0'&&s[i]<='9')
			{
				num=num*10+s[i]-'0';
				i++;
			}
			stk[++top]=num;
		}
		else if(s[i]=='!')
		{
			op[++m]=s[i];
			add(m,stk[top--]);
			stk[++top]=m;
		}
		else if(s[i]=='&'||s[i]=='|')
		{
			op[++m]=s[i];
			add(m,stk[top--]);
			add(m,stk[top--]);
			stk[++top]=m;
		}
	}
	int root=stk[top];
	int sum=dfs1(root);
	dfs2(root);
	cin>>q;
	while(q--)
	{
		int x;
		cin>>x;
		if(vis[x])
		{
			cout<<!sum<<'\n';
		}
		else
		{
			cout<<sum<<'\n';
		}
	}
	return 0;
}
/*
*/