救命！最后6个点TLE

#include<bits/stdc++.h>
using namespace std;

int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

const int N=500010,M=2*N;        //运算符的数量与变量的数量之和最大为500010
string in;      //输入的后缀表达式

int n;          //表达式中变量的个数
bool a[M];     //1~N表达式中变量的值  N+1~2*N每一棵子树的值

int q;          //询问数量

vector<char>c(1);   //存储每一个运算符
int idx;            //记录运算符的个数
int ll[N],rr[N],f[N];
//ll[i]:第i个运算符的左儿子 rr[i]:第i个运算符的右儿子
stack<int>v;        //后缀转中缀使用
void totree() {   //将输入的字符串（后缀表达式）转化为树的结构
    in+=" ";
    int t=0;
    while(in.size()) {
        if(in[0]=='x') {
            t=0;
            for(int i=1; isdigit(in[i]); i++)t=t*10+int(in[i]-'0');
            v.push(t);
        } else {
            int t1,t2;
            t1=v.top();
            v.pop();
            if(in[0]=='&') {
                t2=v.top();
                v.pop();
                c.push_back('&');
                idx++;
                a[idx+N]=a[t1]&&a[t2];
                v.push(N+idx);
                ll[idx]=t1;
                rr[idx]=t2;
            } else if(in[0]=='|') {
                t2=v.top();
                v.pop();
                c.push_back('|');
                idx++;
                a[idx+N]=a[t1]||a[t2];
                v.push(N+idx);
                ll[idx]=t1;
                rr[idx]=t2;
            } else if(in[0]=='!') {
                c.push_back('!');
                idx++;
                a[idx+N]=!a[t1];
                v.push(N+idx);
                ll[idx]=t1;
            }
        }
        while(in[0]!=' ')in.erase(0,1);
        in.erase(0,1);
    }
}

bool g[M];
void fun(int x) {
    g[x]=1;
    if(x<=N)return;
    else {
        x-=N;
        fun(ll[x]);
        fun(rr[x]);
    }
}
void dfs(int x) {
    x-=N;
    switch(c[x]) {
        case '&': {
            if(!a[ll[x]])fun(rr[x]);
            if(!a[rr[x]])fun(ll[x]);
            break;
        }
        case '|': {
            if(a[ll[x]])fun(rr[x]);
            if(a[rr[x]])fun(ll[x]);
            break;
        }
    }
    if(!g[ll[x]]&&ll[x]>N)dfs(ll[x]);
    if(!g[rr[x]]&&rr[x]>N)dfs(rr[x]);
}
int main() {
    getline(cin,in);
    n=read();
    for(int i=1; i<=n; i++)a[i]=read();

    totree();

    dfs(idx+N);

    q=read();
    int x;
    while(q--) {
        x=read();
        if(g[x])cout<<a[idx+N]<<endl;
        else cout<<!a[idx+N]<<endl;
    }
    return 0;
}

求助