Untitled

#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,test;

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


int main(void){
    int N,M,x,y,m,l,r,a;
    Node* root;
    
    scanf("%d",&N);
    root=(Node*)malloc(sizeof(Node)*(N+1));
    root[1].number=1;
    root[1].prev=NULL;
    for(int i=2;i<=N;i++){  
        root[i].number=i;
    }
    for(int i=1;i<=N;i++){   //把tree的線都連好
        scanf("%d %d",&l,&r);
        if(l==0){
            root[i].left=NULL;
        }
        else{
            root[l].prev=&root[i];
            root[i].left=&root[l];
        }
        if(r==0){
            root[i].right=NULL;
        }
        else{
            root[r].prev=&root[i];
            root[i].right=&root[r];
        }
    }

    inorder1(&root[1]);
    inorder2(N);

    scanf("%d",&M);
    for(int i=0;i<M;i++){
        xs=0;//用來記錄字串的數字歸零
        ys=0;
        scanf("%d %d",&x,&y);
        if(x!=1) find(x,1,&root[1]);//如果起點是1就不用找起點到1
        if(y!=1) find(y,0,&root[1]);//如果終點是1就不用找1到終點
        if(x!=1 && y!=1){//如果其中一個是1就不用看是否相同
            for(int j=1;j<=xs && j<=ys;j++){
                if(X[j]==Y[j]){
                    X[j]='\0';
                    Y[j]='\0';
                }
                else{
                    break;
                }
            }
        }

        for(int j=1;j<=xs;j++){//起點到1的這段路有多少印多少個P
            if(X[j]!='\0'){
                printf("P");
                X[j]='\0';
            }
        }
        for(int j=1;j<=ys;j++){//1到終點的這亂如實印出來
            if(Y[j]!='\0'){
                printf("%c",Y[j]);
                Y[j]='\0';
            }
        }
        printf("\n");//萬惡的換行，沒有直接整題爆炸
    }

    return 0;
}

void inorder1(Node* root){ //照著剛剛連好的tree排出一個in-order
    Node* cur=root;

    if(root!=NULL){   //從n=1開始放入，照著in-order的順序放進去，例如，如果in-order是42513那in[1]=4;in[2]=2;in[3]=5;in[4]=1;in[5]=3
        inorder1(root->left);
        n++;
        in[n]=root->number;
        inorder1(root->right);
    }
    return;
}
void inorder2(int N){
    //因為我希望到時候再判斷他們順序的時候，我可以不用一個一個慢慢找，所以:例如我的1在第四個位子，原本我要從in[1]開始找，找到第四個我才找到1
    //但我現在將order[1]設成4，這樣我要找1的時候我就可以馬上知道他在第4個位子
    for(int i=1;i<=N;i++){
        order[in[i]]=i;
    }
}

void find(int m,int w,Node* current){
    Node* cur=current;
   
    if(cur==NULL) return;//如果空的就不用找了

    if(w==1){
        if(order[m]>order[cur->number]){//因為之前把order設為每個數字的位子了，所以直接比它
            xs++;
            X[xs]='R';
            find(m,1,cur->right);//如果m位子比較後面它就在右邊
        }
        else if(order[m]<order[cur->number]){
            xs++;
            X[xs]='L';
            find(m,1,cur->left);//如果m位子比較前面它就在左邊
        }
        else return;
    }
    else{
        if(order[m]>order[cur->number]){
            ys++;
            Y[ys]='R';
            find(m,0,cur->right);
        }
        else if(order[m]<order[cur->number]){
            ys++;
            Y[ys]='L';
            find(m,0,cur->left);
        }
        else return;
    }
}