Codeforces 1010D Mars rover

题目大意：对于一个不完全二分图，根节点为1，叶节点值为0或1，非叶节点包含一个操作（and,or,xor,not），求改变各个叶节点的值时（即0改为1,1改为0），根节点的值是多少

 

解法：遍历图求各节点的值，改变每个叶节点时，向图根节点遍历，求根节点值即可

有两个需要剪枝的地方，一，当改变到当前节点是该节点值已经不在改变，则结束图的向上递归

二，维护每个节点改变时，根节点的值，当再次遍历次节点时，可直接得到答案，结束递归

 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<fstream>
#include<cstdlib>
#include<ctime>
using namespace std;
#define scd(a) scanf("%d",&a)
#define scf(a) scanf("%lf",&a)
#define scl(a) scanf("%lld",&a)
#define sci(a) scanf("%I64d",&a)
#define scs(a) scanf("%s",a)
typedef long long ll;
const int desll[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
const ll mod=1e9+7;
const int maxn=1e6+7;
const int maxm=1e8+7;
const double eps=1e-4;
int m,n,ar[maxn];
char ch[maxn];
int armid[maxn];
struct node{
    int val,num;
    char c;
    node *pre,*l,*r;
    void clear(){
        l=r=NULL;
    }
}no[maxn];
int ma,ans=0;
int newCal(node* u)//求此节点的新值
{
    if(u->c=='N') return 1-(u->l->val);
    else if(u->c=='A') return  u->l->val & u->r->val;
    else if(u->c=='X') return  u->l->val ^ u->r->val;
    else if(u->c=='O') return  u->l->val | u->r->val;
}
void dfs(node* u,int x)
{
    int now=u->val;
    u->val=x;
    if(u->pre == NULL || now == x){//若此节点为根节点或此节点值已经不在改变，结束递归
        ma=1;
        ans=no[1].val;
    }
    else{
        if(armid[u->num]!=-1){//若此节点之前已经被便利过，则直接输出
            ans = armid[u->num];//armid维护每个节点值改变时引起的根节点改变之后的值
            ma=1;
        }
        else{
            dfs(u->pre,newCal(u->pre));
            armid[u->num]=ans;
        }
    }
    u->val=now;
}

void init(node* u)
{
    //cout<<u->val<<endl;
    if(u->c=='I')return ;
    init(u->l);
    if(u->r!=NULL)init(u->r);
    if(u->c=='N')u->val=1-(u->l->val);
    else if(u->c=='A')u->val = u->l->val & u->r->val;
    else if(u->c=='X')u->val = u->l->val ^ u->r->val;
    else if(u->c=='O')u->val = u->l->val | u->r->val;
}
int main()
{
    scd(n);
    int x,y;
    no[1].pre=NULL;
    for(int i=0;i<=n;i++)no[i].clear();
    for(int i=1;i<=n;i++){
        scs(ch);scd(x);
        if(ch[0]=='A' || ch[0]=='O' || ch[0]=='X'){
            scd(y);
            no[i].l=&no[x];
            no[i].r=&no[y];
            no[x].pre = &no[i];
            no[y].pre = &no[i];
            no[i].c=ch[0];
        }
        else if(ch[0]=='N'){
            no[i].l= &no[x];
            no[x].pre = &no[i];
            no[i].c=ch[0];
        }
        else{
            no[i].val=x;
            no[i].c=ch[0];
        }
        no[i].num=i;
    }
    memset(armid,-1,sizeof(armid));
    init(&no[1]);
    int len=0;
    for(int i=1;i<=n;i++){
        ma=0;
        if(no[i].c=='I'){
            dfs(&no[i],1-no[i].val);
            ar[len++]=ans;
        }
    }
    for(int i=0;i<len;i++){
        printf("%d",ar[i]);
    }
    printf("\n");


    return 0;
}