本题找LCA的方法如下:

1. 比较a,b点的层数，如果depth[a]>depth[b]，则a往上移动，否则b往上移动;
2. 循环1，直到a,b移动到同一个节点为止。

代码

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;

const int N = 10010;
int m,n;
int pre[N],inord[N],seq[N];//seq存的是真正的值,而pre,inord中存的是映射过后的下标
int p[N];//存的是节点的父节点
int depth[N];//存的是每个节点的深度
unordered_map<int,int> pos;

int build(int il,int ir,int pl,int pr,int d){
    int root=pre[pl];
    int k=root;
    depth[k]=d;
    if(k>il) p[build(il,k-1,pl+1,pl+1+k-1-il,d+1)]=k;
    if(k<ir) p[build(k+1,ir,pl+1+k-1-il+1,pr,d+1)]=k;
    return root;
}

int main(){
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>pre[i];
        seq[i]=pre[i];
    }
    sort(seq,seq+n);
    for(int i=0;i<n;i++){
        pos[seq[i]]=i;
        inord[i]=i;
    }

    for(int i=0;i<n;i++) pre[i]=pos[pre[i]];

    build(0,n-1,0,n-1,0);

    while(m--){
        int a,b;
        cin>>a>>b;

        if(pos.count(a)&&pos.count(b)){//如果a,b都能够在树中找到
            a=pos[a];b=pos[b];
            int u=a,v=b;
            while(a!=b){
                if(depth[a]>depth[b]) a=p[a];
                else b=p[b];
            }
            if(a!=u&&a!=v) printf("LCA of %d and %d is %d.\n",seq[u],seq[v],seq[a]);
            else if(a==v) printf("%d is an ancestor of %d.\n",seq[v],seq[u]);
            else if(a==u) printf("%d is an ancestor of %d.\n",seq[u],seq[v]);
        }else if(pos.count(a)) printf("ERROR: %d is not found.\n",b);
        else if(pos.count(b)) printf("ERROR: %d is not found.\n",a);
        else printf("ERROR: %d and %d are not found.\n",a,b);
    }

    return 0;
}