算法思路

具体思路可参考二叉树的公共祖先的题解 ，事实上就是一个套用模板的问题。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e4+10;

int m,n;
int u,v;
int in[N],pre[N];
unordered_map<int,int> in_pos;

int LCA(int il,int ir,int pl,int pr){
    int k=in_pos[pre[pl]],up=in_pos[u],vp=in_pos[v];

    if((k-up)*(k-vp)<=0) return pre[pl];
    else if(k>up) return LCA(il,k-1,pl+1,pl+k-il);//u、v都在左子树,向左子树进行递归
    else return LCA(k+1,ir,pl+k-il+1,pr);//u、v都在右子树，向右子树进行递归
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>pre[i];
        in[i]=pre[i];
    }
    sort(in,in+n);
    for(int i=0;i<n;i++) in_pos[in[i]]=i;
    while(m--){
        cin>>u>>v;
        bool f1=in_pos.count(u),f2=in_pos.count(v);
        if(!f1 && !f2) 
            printf("ERROR: %d and %d are not found.\n",u,v);
        else if(!f1) 
            printf("ERROR: %d is not found.\n",u);
        else if(!f2)
            printf("ERROR: %d is not found.\n",v);
        else{
            int ans=LCA(0,n-1,0,n-1);
            if(ans!=u && ans!=v) printf("LCA of %d and %d is %d.\n",u,v,ans);
            else if(ans==u) printf("%d is an ancestor of %d.\n",ans,v);
            else printf("%d is an ancestor of %d.\n",ans,u);
        }
    }
    return 0;
}