正经解题

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <sstream>
#include <algorithm>

using namespace std;

// 节点结构体
struct Node {
int id; // 变量下标，如果是运算符则为 -1, -2, -3
Node* left;
Node* right;
int val; // 当前子表达式的值
bool is_critical; // 该节点的值是否影响最终结果

Node(int i) : id(i), left(nullptr), right(nullptr), val(0), is_critical(false) {}

};

const int OP_AND = -1;
const int OP_OR = -2;
const int OP_NOT = -3;

vector<int> init_vals; // 存储变量的初始值
vector<bool> is_critical_var; // 标记变量是否关键

// 计算节点的值
int evaluate(Node* node) {
if (node->id > 0) {
return node->val = init_vals[node->id];
}

if (node->id == OP_NOT) {
    return node->val = !evaluate(node->left);
} else if (node->id == OP_AND) {
    int l = evaluate(node->left);
    int r = evaluate(node->right);
    return node->val = (l & r);
} else if (node->id == OP_OR) {
    int l = evaluate(node->left);
    int r = evaluate(node->right);
    return node->val = (l | r);
}
return 0;

}

// 标记关键路径
// parent_val: 父节点在“假设当前节点能改变结果”的情况下的期望值（用于剪枝判断）
// is_critical: 当前节点是否处于关键路径上
void mark_critical(Node* node, bool is_critical) {
if (!node) return;

node->is_critical = is_critical;
if (node->id > 0) {
    if (is_critical) {
        is_critical_var[node->id] = true;
    }
    return;
}

if (node->id == OP_NOT) {
    // 取反运算，子节点的变化一定会影响父节点
    mark_critical(node->left, is_critical);
} else if (node->id == OP_AND) {
    if (!is_critical) {
        mark_critical(node->left, false);
        mark_critical(node->right, false);
    } else {
        // 如果当前节点关键，我们要看哪个子节点能改变它
        // 当前节点值为 node->val。
        // 如果左子节点是0，那么结果已经是0，右子节点无论如何都不影响结果。
        // 如果左子节点是1，结果取决于右子节点。
        
        int l_val = node->left->val;
        int r_val = node->right->val;
        
        // 左子树关键当且仅当：右子树值为1（此时左子树决定结果）或者右子树本身不关键但我们需要遍历
        // 更简单的逻辑：
        // 对于 A & B = V。
        // 如果 V == 1，则 A=1, B=1。改变A或B都会改变V。两者都关键。
        // 如果 V == 0。
        //   若 A == 0，则结果由A决定（如果A变1，结果可能变）。B无论如何都是0（除非A也变，但我们一次只变一个）。所以A关键，B不关键。
        //   若 A == 1，则 B == 0。结果由B决定。A不关键，B关键。
        
        if (node->val == 1) {
            mark_critical(node->left, true);
            mark_critical(node->right, true);
        } else {
            if (node->left->val == 0) {
                mark_critical(node->left, true);
                mark_critical(node->right, false);
            } else {
                mark_critical(node->left, false);
                mark_critical(node->right, true);
            }
        }
    }
} else if (node->id == OP_OR) {
    if (!is_critical) {
        mark_critical(node->left, false);
        mark_critical(node->right, false);
    } else {
        // 对于 A | B = V
        // 如果 V == 0，则 A=0, B=0。改变任意一个都会使结果变1。两者都关键。
        // 如果 V == 1。
        //   若 A == 1，结果已为1，B不关键。A关键。
        //   若 A == 0，则 B == 1。结果由B决定。A不关键，B关键。
        
        if (node->val == 0) {
            mark_critical(node->left, true);
            mark_critical(node->right, true);
        } else {
            if (node->left->val == 1) {
                mark_critical(node->left, true);
                mark_critical(node->right, false);
            } else {
                mark_critical(node->left, false);
                mark_critical(node->right, true);
            }
        }
    }
}

}

int main() {
// 优化IO
ios::sync_with_stdio(false);
cin.tie(NULL);

string line;
getline(cin, line);

// 解析后缀表达式建树
stack<Node*> st;
stringstream ss(line);
string token;

while (ss >> token) {
    if (token == "&") {
        Node* r = st.top(); st.pop();
        Node* l = st.top(); st.pop();
        Node* op = new Node(OP_AND);
        op->left = l;
        op->right = r;
        st.push(op);
    } else if (token == "|") {
        Node* r = st.top(); st.pop();
        Node* l = st.top(); st.pop();
        Node* op = new Node(OP_OR);
        op->left = l;
        op->right = r;
        st.push(op);
    } else if (token == "!") {
        Node* l = st.top(); st.pop();
        Node* op = new Node(OP_NOT);
        op->left = l;
        st.push(op);
    } else {
        // 变量 x1, x10...
        int id = stoi(token.substr(1));
        st.push(new Node(id));
    }
}

Node* root = st.top();

int n;
cin >> n;
init_vals.resize(n + 1);
is_critical_var.resize(n + 1, false);

for (int i = 1; i <= n; ++i) {
    cin >> init_vals[i];
}

// 1. 计算初始值
int original_val = evaluate(root);

// 2. 标记关键变量
mark_critical(root, true);

int q;
cin >> q;
while (q--) {
    int x;
    cin >> x;
    // 如果变量是关键变量，翻转结果；否则保持原样
    if (is_critical_var[x]) {
        cout << (1 - original_val) << "\n";
    } else {
        cout << original_val << "\n";
    }
}

return 0;

}