CF1010D Mars rover

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