题解：P11540 [Code+#5] 表达式二叉树填数
FallingFYC_
·
·
题解
P11540 [Code+#5] 表达式二叉树填数
分析
对于一个 01 未知数 x，显然有 0 \operatorname{AND} x=0，1 \operatorname{OR} x=1，不能通过 1 \operatorname{AND} x=y 或 0 \operatorname{OR} x=y 来得出 y 的值。
思路
考虑贪心。
假设询问 P_i 的时间为 i，定义一个节点 A 的 t_A 为：
\max(t_{A的左儿子},t_{A的右儿子}) & A不为叶子节点 \\
i & A=P_i
\end{cases}
所以对于一个非叶节点 $B$：
- 如果它的逻辑运算符为 $\operatorname{AND}$，则它的两个子结点中 $t$ 较小的一个的取值为 $1$，另一个与 $B$ 取值相同。
- 如果它的逻辑运算符为 $\operatorname{OR}$，则它的两个子结点中 $t$ 较小的一个的取值为 $0$，另一个与 $B$ 取值相同。
两遍 dfs 分别得到 $t$ 和结果即可。
注意题目让根节点为 $1$。
---
### 代码
```cpp
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,a,b) for(int i=a;i>=b;i--)
#define psbk push_back
#define mkp make_pair
#define endl '\n'
typedef long long ll;
using namespace std;
const int N=5e5+5;
int n,ask[N<<1],ans[N<<1];
vector<int> e[N<<1];
bool bk[N<<1],op[N];
void dfs1(int u){
bk[u]=1;
if(u<=n)return;
for(auto v:e[u])
if(!bk[v]){
dfs1(v);
ask[u]=max(ask[u],ask[v]);
}
}
void dfs2(int u){
bk[u]=1;
if(u<=n)return;
int mint=1e9,minp;
for(auto v:e[u])
if(!bk[v]&&ask[v]<mint)mint=ask[v],minp=v;
ans[minp]=(op[u-n]?0:1);
for(auto v:e[u])
if(!bk[v]){
if(v!=minp)ans[v]=ans[u];
dfs2(v);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
FOR(i,1,n-1)cin>>op[i];
FOR(i,1,2*n-2){
int u,v;
cin>>u>>v;
e[u].psbk(v),e[v].psbk(u);
}
FOR(i,1,n){
int u;
cin>>u;
ask[u]=i;
}
dfs1(n+1);
memset(bk,0,sizeof bk);
memset(ans,0x3f,sizeof ans);
ans[n+1]=1;
dfs2(n+1);
FOR(i,1,n)cout<<ans[i];
return 0;
}
```