rt

code:

#include<bits/stdc++.h>
using namespace std;
struct node
{
    char x;
    bool value;
    int lchild,rchild,fa;
}tree[1000005];
string s;
int n,m,k,q,u,tmp,a[100005];
bool x[100005],fw[1000005];
stack<int>sta;
void DFS(int root)
{
    switch(tree[root].x)
    {
        case 'x':
            return;
        case '&':
            if(!tree[tree[root].lchild].value) //判断是否影响最终答案
                fw[tree[root].rchild]=true;
            if(!tree[tree[root].rchild].value)
                fw[tree[root].lchild]=true;
            DFS(tree[root].lchild);
            DFS(tree[root].rchild);
            break;
        case '|':
            if(tree[tree[root].lchild].value) //判断是否影响最终答案
                fw[tree[root].rchild]=true;
            if(tree[tree[root].rchild].value)
                fw[tree[root].lchild]=true;
            DFS(tree[root].lchild);
            DFS(tree[root].rchild);
            break;
        case '!':
            if(fw[root])fw[tree[root].lchild]=true;
            DFS(tree[root].lchild);
            break;
    }
}
bool check(int root)
{
    for(int i=root;i!=-1;i=tree[i].fa)
        if(fw[i])return true;
    return false;
}
int main()
{
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
    getline(cin,s);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>x[i];
    for(int i=0;i<s.size();) //解析字符串
    {
        if(s[i]=='x') //处理变量
        {
            tmp=0,i++;
            while(s[i]>='0'&&x[i]<='9')
                tmp=tmp*10+(s[i++]-'0');
            tree[tmp]=(node){'x',x[tmp],-1,-1,-1};
            a[++m]=tmp,i++;
            continue;
        }
        if(s[i]=='&') //处理与运算
        {
            tree[n+(++k)]=(node){'&',false,-1,-1,-1};
            a[++m]=n+k,i+=2;
            continue;
        }
        if(s[i]=='|') //处理或运算
        {
            tree[n+(++k)]=(node){'|',false,-1,-1,-1};
            a[++m]=n+k,i+=2;
            continue;
        }
        if(s[i]=='!') //处理非运算
        {
            tree[n+(++k)]=(node){'!',false,-1,-1,-1};
            a[++m]=n+k,i+=2;
            continue;
        }
    }
    for(int i=1;i<=m;i++) //建表达式树
    {
        if(a[i]<=n)
            sta.push(a[i]);
        else
        {
            if(tree[a[i]].x=='&') //处理与运算
            {
                int t1=sta.top();sta.pop();
                int t2=sta.top();sta.pop();
                tree[a[i]]=(node){'&',tree[t1].value&&tree[t2].value,t1,t2,tree[a[i]].fa};
                sta.push(a[i]),tree[t1].fa=tree[t2].fa=a[i];
            }
            else if(tree[a[i]].x=='|') //处理或运算
            {
                int t1=sta.top();sta.pop();
                int t2=sta.top();sta.pop();
                tree[a[i]]=(node){'|',tree[t1].value||tree[t2].value,t1,t2,tree[a[i]].fa};
                sta.push(a[i]),tree[t1].fa=tree[t2].fa=a[i];
            }
            else //处理非运算
            {
                int t=sta.top();sta.pop();
                tree[a[i]]=(node){'!',!tree[t].value,t,-1,tree[a[i]].fa};
                sta.push(a[i]),tree[t].fa=a[i];
            }
        }
    }
    DFS(sta.top());
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        bool ans;
        cin>>u;
        if(check(u))ans=tree[sta.top()].value;
        else ans=!tree[sta.top()].value;
        cout<<ans<<'\n';
    }
    return 0;
}