C++ 代码

// 常规思路

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int m, n;
int l[N], r[N], v[N]; 
unordered_set<int> check; // 用于标记某个值有无出现过
int father;

// 构建树
int build(int lt, int rt) {
    if(lt > rt) return -1;
    int w = v[lt];
    int i = lt + 1;
    for(;i <= rt;i ++) {
        if(v[i] >= w) {
            break;
        }
    }
    l[lt] = build(lt + 1, i - 1);
    r[lt] = build(i, rt);
    return lt;
}  

// 查找
void dfs(int u, int a, int b) {
// 当已经找到父节点就没必要继续查找，直接返回
// 或者节点不存在也直接返回
    if(father != -1 || u == -1) return ; 
    if(a <= v[u] && v[u] <= b) {
        father = u;
        return ;
    }
    if(v[u] > b) dfs(l[u], a, b);
    else if(v[u] <= a) dfs(r[u], a, b);
}

int main() {
    cin >> m >> n;
    for(int i = 0;i < n;i ++) {
        cin >> v[i];
        check.insert(v[i]);
    }

    build(0, n - 1);
    for(int i = 0;i < m;i ++) {
        father = -1;
        int a, b;
        cin >> a >> b;
        int p = a, q = b;
        if(p > q) swap(p, q);
        dfs(0, p, q);
        if(!check.count(a) && !check.count(b)) printf("ERROR: %d and %d are not found.\n", a, b);
        else if(!check.count(a)) printf("ERROR: %d is not found.\n", a);
        else if(!check.count(b)) printf("ERROR: %d is not found.\n", b);
        else if(v[father] == a)  printf("%d is an ancestor of %d.\n", a, b);
        else if(v[father] == b)  printf("%d is an ancestor of %d.\n", b, a);
        else printf("LCA of %d and %d is %d.\n", a, b, v[father]);
    }   
    return 0;
}

写完之后看题解：还是这位佬写的妙：

https://www.acwing.com/solution/content/13398/

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int m, n;
int v[N];
unordered_set<int> check;

int main() {
    cin >> m >> n;
    for(int i = 0;i < n;i ++) {
        cin >> v[i];
        check.insert(v[i]);
    }

    for(int i = 0;i < m;i ++) {
        int a, b;
        cin >> a >> b;

        if(!check.count(a) && !check.count(b)) printf("ERROR: %d and %d are not found.\n", a, b);
        else if(!check.count(a)) printf("ERROR: %d is not found.\n", a);
        else if(!check.count(b)) printf("ERROR: %d is not found.\n", b);
        else {
            int father;
            for(int j = 0;j < n;j ++) {
                if((a <= v[j] && v[j] <= b) || (b <= v[j] && v[j] <= a)) {
                    father = v[j];
                    break;
                }
            }
            if(father == a || father == b)  printf("%d is an ancestor of %d.\n", father, father == a ? b : a);
            else printf("LCA of %d and %d is %d.\n", a, b, father);
        }
    }   
    return 0;
}