知识点：表达式求值、链式前向星 分析： 由题意得，题目的表达式是后缀表达式，所以可以用栈建立一棵表达式树，然后从根结点向下递归求出表达式树的值。 因为计算过程只会出现逻辑运算，所以就可以利用'&'、'|'运算的短路性质，预处理出每个结点u的左右儿子发生变化时，是否影响到了最终的计算结果，即表达式的值。这样，每次询问就能在O(1)的时间复杂度内返回答案。 预处理出每个结点u的左右儿子发生变化时，我们可以对根结点的影响可以使用两次DFS： 第一次DFS求出所有非叶子结点u的值w[u]和表达式的值 第二次DFS求所有非叶子结点的值发生变化时能够影响到根结点的值： 如果当前运算符是'!'，子结点发生变化，就能影响到根结点的值 如果当前运算符是'&'，两个子结点分别为a和b，如果w[a]是1，b结点发生变化，就能影响到根结点的值；如果w[b]是1，a结点发生变化，就能影响到根结点的值； 如果当前运算符是'|'，两个子结点分别为a和b，如果w[a]是0，b结点发生变化，就能影响到根结点的值；如果w[b]是0，a结点发生变化，就能影响到根结点的值 AC代码 欢迎加入团队

首先输入的一坨字符串要先解析，利用栈来建表达式树 对于非运算，我直接用德·摩根定律，下传标记让子树信息都反一下。（其实没必要，当初这样写是因为觉得每个结点都二叉比较美，方便后续处理） 题目里有个信息是“每个变量在表达式中出现恰好一次”，而每个询问只改变一个变量的值，这对原答案来说就产生两个可能：变或不变。这听起来是一句废话，其实蕴含的意思是：有些变量对整个表达式其决定作用，其改变则原答案也改变；有些变量对整个表达式根本没用，其变不变原答案都不变。 说明白一点，就是1 & x = x ，0 | x= x ，这两个公式里的 x 就起了决定性作用，而 0 & x = 0 ，1 | x= 1 的 x 就是一个**。 那我们就给树上每个结点建一个**标记，对& 来说，如果一棵子树是 0，那另外一棵子树内所有叶结点都应该打上**标记，对|同理。 先计算出原表示答案ans，这样我们在查询的时候，没被标记的就说明它往上到根节点都不存在一种让它变成**的运算，所以答案是!ans，如果有标记则答案依旧为ans。

首先这道题给了后缀表达式，那我们就先建树 建完树后，分析样例 题中有一点提示了思路（每次改变都是一次性的） 也就是说我们只需要判断这个点是否会改变表达式的值 通过分析可知在 x|0 和 x&1 时不会使其父亲节点改变，其余情况则会改变 那么我们就可以据此写出递归函数，用vis数组标记改点是否会影响根节点 最后根据问题输出即可 防止ctrl a+ctrl c +ctrl +v AC代码不予展示

题意分析 给定一个后缀逻辑表达式，其中有若干变量，给定变量初始值，问哪些变量单独改变会对整个表达式的结果造成影响 具体思路 建图部分： 遍历字符串，通过空格将字符串分割成若干元素，将元素编号后一一塞入栈中，若是变量则作为叶子节点，若当前元素为单目运算符（!）就提出前一元素作为该节点的左节点，若为双目运算符（&和|）就提出前二元素分别作为该节点的左节点与右节点。同时为了后续操作，我们也记录下每个叶子节点的编号所对应的变量，即v[i]表示节点i对应的变量，若不是叶子节点则默认值为0。 第一遍dfs： 为了后续计算哪些变量取反会影响整个表达式，我们需要首先得知树中以每个节点为根的子树所表示的表达式的值，我们定义这些表达式为"子表达式"，并定义以某一子树的根的父节点为根的树为这一子树表示表达式的"父表达式"，dist[i]表示以i为根的子树所表示表达式的值。我们将问题拆分为类似动态规划的子问题，x_value[i]表示变量i的初始值，若x是叶子节点，则dist[x]=x_value[v[x]]的值，否则根据其叶子节点的值逐步往上推。根据这个思路，我们就能在dfs递归的"归"过程中算出所有"子表达式"的值。 第二遍dfs： 根据牢马亡教的小学三年级知识，我们知道形如1&x或0|x的表达式中，x的值会影响表达式的结果。因此，在第二遍dfs中，我们无视单目运算符（!），因为我们的目标是找到所有改变会影响总值的叶子节点，并且已经得知每个"子表达式"的值，并不需要用到它。当遇到双目运算符时，依据dist中存储的左右子树的值，我们可以判断出当前表达式是否是形如1&x或0|x的表达式，并以此判断出左右子树的值是否影响当前表达式的结果。对影响结果的那一棵子树进行搜索，当你的dfs发现自己在叶子节点上时，就说明这个叶子节点的改变会影响整个表达式的值。将结果储存在is_turn数组中。 收尾： 对于每一组询问，只需要依照is_turn数组输出原表达式或取反的结果即可。 AC代码 时间复杂度 线性，O(∣s∣+N+q)O(\lvert s\rvert + N + q)O(∣s∣+N+q)，其中∣s∣\vert s\vert∣s∣表示字符串sss的长度，NNN表示树节点数(变量数nnn+逻辑符号数量)，可以处理较大范围数据。

#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; // 该节点的值是否影响最终结果 }; 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]; } } // 标记关键路径 // parent_val: 父节点在“假设当前节点能改变结果”的情况下的期望值（用于剪枝判断） // is_critical: 当前节点是否处于关键路径上 void mark_critical(Node* node, bool is_critical) { if (!node) return; } int main() { // 优化IO ios::sync_with_stdio(false); cin.tie(NULL); }