题解：P7073 [CSP-J2020] 表达式

这道题是一道非常难的关于树的题目。

前置芝士

思路

我们要先字符串处理（也就是输入，预处理等事情。较简单，不在此描述了）。接着，我们在建一颗表达式树。我们假设在每次询问时，都修改表达式树，然后算出结果。这时我们会发现 TLE 了，因为每次遍历都是 \(\mathcal O(n q)\)，所以我们用到了树形 DP。大多数题目树形 DP 都是从下往上做，但是这道题得从上往下做。然后我们假设 \(u\) 这个节点发生了变化，我们要看它的父亲节点是否有变化。如果没有，最后结果不变；如果父亲节点的值变了，就看这个父亲节点是否会导致父亲节点的父亲的值改变，然后一直做这个操作。最后我们把答案都预处理出来就好啦！

还有很多细节，看代码吧！

AC code:

#include <bits/stdc++.h>
using namespace std;
const int N=1010000;
struct node{int l,r;int type;int val;bool dp;
}a[N];
stack <int> s;
int n,m,q;
int p[N];
void dfs1(int u){if(a[u].type>0)return;if(a[u].type==-1){dfs1(a[u].l);a[u].val= !a[a[u].l].val;}else{dfs1(a[u].l);dfs1(a[u].r);if(a[u].type==-2)a[u].val=a[a[u].l].val & a[a[u].r].val;elsea[u].val=a[a[u].l].val | a[a[u].r].val;}
}
void dfs2(int u){if(a[u].type>0)return;int L=a[u].l,R=a[u].r;if(a[u].type==-1){a[L].dp=a[u].dp;dfs2(L);}else{if(a[u].type==-2){if(a[R].val==0)a[L].dp=false;else a[L].dp=a[u].dp;if(a[L].val==0)a[R].dp=false;else a[R].dp=a[u].dp;}else{if(a[R].val==1)a[L].dp=false;else a[L].dp=a[u].dp;if(a[L].val==1)a[R].dp=false;else a[R].dp=a[u].dp;}dfs2(L);dfs2(R);}
}
int main(){while(true){char ch; scanf("%c",&ch);if(ch=='x'){++n;int id=0;while(true){scanf("%c",&ch);if(ch>='0'&&ch<='9')id=id*10+ch-'0';else break;}a[n].type=id;p[id]=n;s.push(n);}else{assert((ch=='|')||(ch=='&')||(ch=='!'));if(ch=='|'||ch=='&'){++n;int r=s.top();s.pop();int l=s.top();s.pop();a[n].l=l;a[n].r=r;if(ch=='|')a[n].type=-3;else a[n].type=-2;s.push(n);}else{++n;int l=s.top();s.pop();a[n].l=l;a[n].type=-1;s.push(n);}scanf("%c",&ch);}if(ch!=' ')break;}int root=s.top();scanf("%d",&m);for(int i=1;i<=m;i++){int x;scanf("%d",&x);a[p[i]].val=x;}dfs1(root);a[root].dp=true;dfs2(root);scanf("%d",&q);for(int i=0;i<q;i++){int x;scanf("%d",&x);if(a[p[x]].dp)printf("%d\n",a[root].val^1);else printf("%d\n",a[root].val);}
}