自动搬运

查看原文

来自洛谷，原作者为

	FallingFYC_ 但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。

搬运于2025-08-24 23:08:14，当前版本为作者最后更新于2025-01-17 13:24:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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$ 为：

$$t_A=\begin{cases} \max(t_{A的左儿子},t_{A的右儿子}) & A不为叶子节点 \\ i & A=P_i \end{cases}$$

$t_A$ 的意义为节点 $A$ 在最坏情况下获得取值的时间。

所以对于一个非叶节点 $B$：

• 如果它的逻辑运算符为 $\operatorname{AND}$，则它的两个子结点中 $t$ 较小的一个的取值为 $1$，另一个与 $B$ 取值相同。
• 如果它的逻辑运算符为 $\operatorname{OR}$，则它的两个子结点中 $t$ 较小的一个的取值为 $0$，另一个与 $B$ 取值相同。

两遍 dfs 分别得到 $t$ 和结果即可。

注意题目让根节点为 $1$。

---

代码

#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;
}