2，4，13，16，20AC。 使用二叉树+栈+递归

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
struct bt
{
	int l,r;
}tree[1000001];
int x[100001],a[100001],len,sum,n,q,t;
int flag[100001];
bool f[100001];
string bd;
stack<int>s;
int js(int now,int g)
{
	a[now]^=g;
	if(now<=n)
		return a[now];
	int x=js(tree[now].l,g^flag[tree[now].l]);
	int y=js(tree[now].r,g^flag[tree[now].r]);
	if(a[now]==2)
	{
		if(x==0) 
			f[tree[now].r]=1;
		if(y==0)
			f[tree[now].l]=1;
		return x&y;
	}
	else
	{
		if(x==1) 
			f[tree[now].l]=1;
		if(y==1)
			f[tree[now].r]=1;
		return x|y;
	}
}
void dfs(int now)
{
	if(now<=n) return;
	f[tree[now].l]|=f[now];
	f[tree[now].r]|=f[now];
	dfs(tree[now].l);
	dfs(tree[now].r);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	getline(cin,bd);
	len=bd.size();
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>x[i];
	sum=n;
	for(int i=0;i<len;i++)
	{
		
		if(bd[i]=='x')
		{
			int cnt=0;
			i++;
			while(bd[i]!=' ')
				cnt=cnt*10+(bd[i]-'0'),i++;
			i--;
			s.push(cnt);
		}
		if(bd[i]=='&')
		{
			int x=s.top();s.pop();
			int y=s.top();s.pop();
			s.push(++sum);
			a[sum]=2;
			tree[sum]={x,y};
		}
		if(bd[i]=='|')
		{
			int x=s.top();s.pop();
			int y=s.top();s.pop();
			s.push(++sum);
			a[sum]=3;
			tree[sum]={x,y};
		}
		if(bd[i]=='!')
			flag[s.top()]^=1;
	}
	int ans=js(sum,flag[sum]);
	dfs(sum);
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>t;
		if(f[t])
			cout<<!ans<<endl;
		else
			cout<<ans<<endl;
	}
	return 0;
}

谢谢大佬！