Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.2 kB
0
Indexable
Never
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int child[200005][2];
int idx[200005];
int p[200005];
int ans;

void sol(int root,int l,int r){
    if(!ans) return;

    if(child[root][0] && child[root][1]){
        if((idx[child[root][0]] >idx[root] && idx[child[root][0]]<=r) && (idx[child[root][1]] <idx[root] && idx[child[root][1]]>=l)){
            sol(child[root][0],idx[root]+1,r);
            sol(child[root][1],l,idx[root]-1);
        }
        else if((idx[child[root][1]] >idx[root] && idx[child[root][1]]<=r) && (idx[child[root][0]] <idx[root] && idx[child[root][0]]>=l)){
            sol(child[root][1],idx[root]+1,r);
            sol(child[root][0],l,idx[root]-1);
        }else ans=0;
    }
    else if(child[root][0]){
        if(idx[child[root][0]] >idx[root] && idx[child[root][0]]<=r){
            sol(child[root][0],idx[root]+1,r);
        }
        else if(idx[child[root][0]] <idx[root] && idx[child[root][0]]>=l){
            sol(child[root][0],l,idx[root]-1);
        }else ans=0;
    }
    else if(child[root][1]){
        if(idx[child[root][1]] >idx[root] && idx[child[root][1]]<=r){
            sol(child[root][1],idx[root]+1,r);
        }
        else if(idx[child[root][1]] <idx[root] && idx[child[root][1]]>=l){
            sol(child[root][1],l,idx[root]-1);
        }else ans=0;
    }
    else return;
}

int main(void){
    int N;
    while(scanf("%d",&N)!=EOF){
        ans=1;
        for(int i=0;i<=N;i++){
            p[i]=0;
            idx[i]=0;
            child[i][0]=0;
            child[i][1]=0;
        }
        for(int i=1;i<=N;i++){
            scanf("%d %d",&child[i][0],&child[i][1]);
            p[child[i][0]]=i;
            p[child[i][1]]=i;
        }
        for(int i=1;i<=N;i++){
            int num;
            scanf("%d",&num);
            idx[num]=i;
        }
        int root;
        for(int i=1;i<=N;i++){
            if(!p[i]){
                root=i;
                break;
            }
        }
        sol(root,1,N);
        if(ans) printf("YES\n");
        else printf("NO\n");
    }
    return 0;  
}