题解：树形+递归

首先这道题给了后缀表达式，那我们就先建树

for(int i=0;i<s.size();i++){
        if(s[i]=='x'){
            int x=0;
            i++;
            while(s[i]<='9'&&s[i]>='0'){
                x=x*10+s[i]-'0';
                i++;
            }
            stk.push(x);
            i--;
        }
        if(s[i]=='!'){
            int k=stk.top();
            a[k]=!a[k];
        }
        if(s[i]=='|'){
            int r=stk.top();
            stk.pop();
            int l=stk.top();
            stk.pop();
            a[++p]=a[l]|a[r];
            son[p][0]=l;
            son[p][1]=r;
            son[p][2]=0;
            stk.push(p);
        }
        if(s[i]=='&'){
            int r=stk.top();
            stk.pop();
            int l=stk.top();
            stk.pop();
            a[++p]=a[l]&a[r];
            son[p][0]=l;
            son[p][1]=r;
            son[p][2]=1;
            stk.push(p);
        }
    }

建完树后，分析样例
题中有一点提示了思路（每次改变都是一次性的）
也就是说我们只需要判断这个点是否会改变表达式的值

通过分析可知在 x|0 和 x&1 时不会使其父亲节点改变，其余情况则会改变
那么我们就可以据此写出递归函数，用vis数组标记改点是否会影响根节点

void dfs(int u,int k){
    int l=son[u][0],r=son[u][1],c=son[u][2];
    if(l==0&&r==0)return ;
    if(k==0){
//若其父节点不会对根节点产生影响，那么其子节点也一定不会对根节点造成影响
        vis[l]=vis[r]=0;
        dfs(l,0);
        dfs(r,0);
    }
    else{
        if(c==0){
            if(a[l]==1){
                vis[r]=0;
                dfs(r,0);
            }
            else{
                vis[r]=1;
                dfs(r,1);
            }
            if(a[r]==1){
                vis[l]=0;
                dfs(l,0);
            }
            else{
                vis[l]=1;
                dfs(l,1);
            }
                
        }
        if(c==1){
            if(a[l]==0){
                vis[r]=0;
                dfs(r,0);
            }
            else{
                vis[r]=1;
                dfs(r,1);
            }
            if(a[r]==0){
                vis[l]=0;
                dfs(l,0);
            }
            else{
                vis[l]=1;
                dfs(l,1);
            }
        }
    }
    
}

最后根据问题输出即可

防止ctrl a+ctrl c +ctrl +v AC代码不予展示