FOGGY

记忆化搜索

改变每一个叶子节点，它的影响是线性的往根节点走

也就是说，如果一个父节点在这条路径上改变了，并且这种改变会影响到根节点那么应该标记，

同理，没有影响的改变

也就是说，标记某个节点的改变的影响

那么怎么具体搞呢

对于每一种操作，单独分析

$O(n^2)$

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
string s;
const int maxn=1e6+5;
struct ed{
    int to;
    int ne;
} edg[maxn*2];
struct p{
    int son[3];
    int op;
    int v;
    int f;
}po[maxn*4];
int fa[maxn];
int leaf[maxn];
int x,y;
int head[maxn];
int pp; 
void add(int x,int y){
    pp++;
    edg[pp].ne=head[x];
    edg[pp].to=y;
    head[x]=pp;
    return ;
}
void dfs(int r,int fa){
    for(int i=head[r];i;i=edg[i].ne){
        if(edg[i].to!=fa){
            dfs(edg[i].to,r);
        }
    }
    if(po[r].op==1){
        po[r].v=po[po[r].son[1]].v&po[po[r].son[2]].v;
    }
    if(po[r].op==2){
        return ;
    }
    if(po[r].op==3){
        po[r].v=po[po[r].son[1]].v^po[po[r].son[2]].v;
    }
    if(po[r].op==4){
        po[r].v=po[po[r].son[1]].v|po[po[r].son[2]].v;
    }
    if(po[r].op==5){
        po[r].v=!po[po[r].son[1]].v;
    }
    return ;
}
int a;
bool dfss(int r,int la,int lv){
    if(la==0&&lv==0){
        return dfss(fa[r],r,!po[r].v); 
    }
    if(r==n+1){
        return 1;
    }
    int tem;
    if(po[r].op==1){
        for(int i=1;i<=2;++i){
            if(po[r].son[i]!=la){
                tem=po[po[r].son[i]].v;
            }
        }
        if(tem==1&&lv==1){
            if(po[r].f!=-1)
            return po[r].f;
            else
            return po[r].f=dfss(fa[r],r,1);
        }else
        if(tem==1&&lv==0){
            if(po[r].f!=-1)
            return po[r].f;
            else
            return po[r].f=dfss(fa[r],r,0);
        }else{
            return 0;
        }
    }
    if(po[r].op==3){
        for(int i=1;i<=2;++i){
            if(po[r].son[i]!=la){
                tem=po[po[r].son[i]].v;
            }
        }
        if(po[r].f!=-1)
            return po[r].f;
        else
            return po[r].f=dfss(fa[r],r,tem^lv);
    }
    if(po[r].op==4){
        for(int i=1;i<=2;++i){
            if(po[r].son[i]!=la){
                tem=po[po[r].son[i]].v;
            }
        }
        if(tem==1){
            return 0;
        }
        if(tem==0){
            if(po[r].f!=-1)
            return po[r].f;
            else
            return po[r].f=dfss(fa[r],r,tem|lv);
        } 
    }
    if(po[r].op==5){
        if(po[r].f!=-1)
            return po[r].f;
        else
            return po[r].f=dfss(fa[r],r,!po[r].v);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        cin>>s;
        po[i].f=-1;
        if(s=="AND"){
            scanf("%d%d",&x,&y);  
            add(x,i);
            add(y,i);
            add(i,x);
            add(i,y);
            fa[x]=i;
            fa[y]=i;
            po[i].son[1]=x;
            po[i].son[2]=y;
            po[i].op=1;
        }
        if(s=="IN"){
            scanf("%d",&x);
            po[i].op=2;
            po[i].v=x;
            a++;
            leaf[a]=i;
        }
        if(s=="XOR"){
            scanf("%d%d",&x,&y);  
            add(x,i);
            add(y,i);
            add(i,x);
            add(i,y);
            fa[x]=i;
            fa[y]=i;
            po[i].son[1]=x;
            po[i].son[2]=y;
            po[i].op=3;
        }
        if(s=="OR"){
            scanf("%d%d",&x,&y);  
            add(x,i);
            add(y,i);
            add(i,x);
            fa[x]=i;
            fa[y]=i;
            add(i,y);
            po[i].son[1]=x;
            po[i].son[2]=y;
            po[i].op=4;
        }
        if(s=="NOT"){
            scanf("%d",&y);   
            add(y,i);
            add(i,y);
            fa[y]=i;
            po[i].son[1]=y;
            po[i].op=5;
        }
    }
    dfs(1,0);
    fa[1]=n+1;
    for(int i=1;i<=a;++i){
        if(dfss(leaf[i],0,0))
        printf("%d",!po[1].v);
        else
        printf("%d",po[1].v);
    }
    return 0;
}