Untitled

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

typedef struct _Node{
    int number;
    struct _Node *left,*right,*prev;
}Node;

int in[3005];
int order[3005];
char X[3005];
char Y[3005];

int n,xs,ys;

void inorder1(Node* root);
void inorder2(int N);
void find(int m,int w,Node* cur);


int main(void){
    int N,M,x,y,m;
    Node* root;
    
    scanf("%d",&N);
    root=(Node*)malloc(sizeof(Node)*(N+2));
    root[1].number=1;
    root[1].prev=NULL;
    for(int i=0,j=1;i<=N;i+=2,j++){
        scanf("%d %d",&root[i].number,&root[i+1].number);
        root[i].prev=&root[j];
        root[i+1].prev=&root[j];
        root[j].left=&root[i];
        root[j].right=&root[i+1];
    }

    inorder1(root);
    inorder2(N);

    scanf("%d",&M);
    for(int i=0;i<M;i++){
        xs=0;
        ys=0;
        scanf("%d %d",&x,&y);
        find(x,1,root);
        find(y,0,root);
        for(int j=0;j<=xs && j<=ys;j++){
            if(X[j]==Y[j]){
                X[j]='\0';
                Y[j]='\0';
            }
            else break;
        }
        for(int j=0;j<=xs;j++){
            if(X[j]!='\0'){
                printf("P");
                X[j]='\0';
            }
            else break;
        }
        for(int j=0;j<=ys;j++){
            if(X[j]!='\0'){
                printf("%c",Y[j]);
                Y[j]='\0';
            }
            else break;
        }
        printf("\n");
    }

    return 0;
}

void inorder1(Node* root){
    Node* cur=root;

    if(root->left!=NULL) inorder1(root->left);
    n++;
    in[n]=root->number;
    if(root->right!=NULL) inorder1(root->right);

    return;
}
void inorder2(int N){

    for(int i=1;i<=N;i++){
        order[in[i]]=i;
    }
}

void find(int m,int w,Node* cur){
    if(cur==NULL) return;

    if(w==1){
        if(order[m]>order[cur->number]){
            X[xs]='R';
            find(m,1,cur->right);
        }
        else if(order[m]<order[cur->number]){
            X[xs]='L';
            find(m,1,cur->left);
        }
    }
    else{
        if(order[m]>order[cur->number]){
            Y[ys]='R';
            find(m,0,cur->right);
        }
        else if(order[m]<order[cur->number]){
            Y[ys]='L';
            find(m,0,cur->left);
        }
    }
}