题目描述

树中两个结点 U 和 V 的最低公共祖先（LCA）是指同时具有 U 和 V 作为后代的最深结点。

二叉搜索树 (BST) 递归定义为具有以下属性的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉搜索树
现在给定 BST 中的任意两个结点，请你找出它们的最低公共祖先。

输入格式
第一行包含两个整数 M 和 N，分别表示询问结点对数以及二叉搜索树中的结点数量。

第二行包含 N 个不同整数，表示该二叉搜索树的前序遍历序列。

接下来 M 行，每行包含两个不同的整数 U 和 V，表示一组询问。

所有结点权值均在 int 范围内。

输出格式
对于每对给定的 U 和 V，输出一行结果。

如果 U 和 V 的 LCA 是 A，且 A 不是 U 或 V，则输出 LCA of U and V is A.。

如果 U 和 V 的 LCA 是 A，且 A 是 U 或 V 中的一个，则输出 X is an ancestor of Y.，其中 X 表示 A，Y 表示另一个结点。

如果 U 或 V 没有在 BST 中找到，则输出 ERROR: U is not found. 或 ERROR: V is not found. 或 ERROR: U and V are not found.。

数据范围

1≤M≤1000,
1≤N≤10000

输入样例：

6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99

输出样例：

LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

感受：

倍增加ST表求LCA就很好用了，但是今天看到了tarjan算法求LCA，tarjan真是啥都会。。。
找了这个板子题试了试，欸！这个不是板子题，多了个离散化，哇，写了一个半小时，坑死了这个离散化；
关于离散：用map，两个，一个正向映射，一个反向；
关于前向星：初始化数据很奇怪是因为怕有结点值[0]出现，其实我也不知道0的出现会不会导致程序逻辑出错，
反正这样肯定不会错，除非数据又出现正无穷，那。。。
这是个人练习tarjan算法的代码，比较丑，不幸看到本题解的小伙伴建议使用ST，打个表就完事了，简单易懂，
不过好像还是要map映射哈，反正本题考的是LCA，但是最让人头疼的还是这个离散，LCA本身不会太难；
如果不想这么麻烦也可以像一楼大佬那样靠BST的性质解题；

C++ 代码

#include<algorithm>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<iostream>
#include<vector>
#define Lson (root<<1)
#define Rson (root<<1|1)

const int space = 1e4 + 7;
int M, N;//分别表示询问结点对数以及二叉搜索树中的结点数量。
int mid[space] = {}, pre[space] = {};
int head[space] = {}, nxt[space << 3] = {}, ver[space << 3] = {}, tot = 0;
std::map<int, int>ali, love, reser;
std::map<std::pair<int, int>, int>ans;//存答案
int ques[space][2] = { {} }, st[space] = {}, vis[space] = {}, tlj[space][2] = { {} };
//ques存问题结点的逻辑，0表示该节没出现过，99表示表示两个结点都合理，1表示该节点出现过，99好像没用到
//st——set tajan部分，tlj结点反向映射后的值，即原来的真实值
void addEdge(int a, int b) { nxt[++tot] = head[a], head[a] = tot, ver[tot] = b; }
int find(int now) { if (st[now] == now)return now; else return st[now] = find(st[now]); }
struct kk { int data; kk* left, * right; };

void tarjanFindLCA(kk *root,int fa)
{
    if (root->left)tarjanFindLCA(root->left, love[root->data]);
    if (root->right)tarjanFindLCA(root->right, love[root->data]);
    for (int i = head[love[root->data]]; 0x3f3f3f3f != i; i = nxt[i])
    {
        int yr = ver[i];
        if (vis[yr])
        {
            std::pair<int, int> tmp;
            tmp.first = love[root->data];
            tmp.second = yr;
            if (tmp.first > tmp.second)std::swap(tmp.first, tmp.second);
            ans[tmp] = reser[find(yr)];
        }
        else if (yr == love[root->data])ans[{yr, yr}] = reser[find(yr)];
    }
    st[love[root->data]] = fa;
    vis[love[root->data]] = 1;
}

void buildTree(kk*& root, int* pre, int* mid, int len)//前中还原
{
    if (!len)return;
    root = new kk;
    root->data = pre[0];
    root->left = root->right = NULL;
    if (1 == len)return;
    int i = 0;
    for (; i < len; i++)
        if (mid[i] == pre[0])
        {
            buildTree(root->left, pre + 1, mid, i);
            buildTree(root->right, pre + i + 1, mid + i + 1, len - i - 1);
        }
}

int main(void)
{
    std::ios_base::sync_with_stdio(false);
    memset(head, 0x3f3f3f3f, sizeof(head));
    kk* tree;
    std::cin >> M >> N;
    for (int i = 1; i <= N; i++)std::cin >> mid[i], pre[i] = mid[i], ali[mid[i]] = 1, st[i] = i;
    std::sort(mid + 1, mid + 1 + N);
    for (int i = 1; i <= N; i++)love[mid[i]] = i, reser[i] = mid[i];
    buildTree(tree, pre + 1, mid + 1, N);

    for (int i = 1; i <= M; i++)
    {
        int a, b, f1 = 0, f2 = 0;
        std::cin >> a >> b;
        if (!ali[a])ques[i][0] = false;
        else ques[i][0] = true, f1 = 1;
        if (!ali[b])ques[i][1] = false;
        else ques[i][1] = true, f2 = 1;
        if (f1 && f2)
        {
            ques[i][0] = 99;
            addEdge(love[a], love[b]), addEdge(love[b], love[a]);
        }
        //if (a > b)std::swap(a, b);
        tlj[i][0] = a, tlj[i][1] = b;
    }

    tarjanFindLCA(tree, love[tree->data]);

    for (int i = 1; i <= M; i++)
    {
        if (!ques[i][0] && !ques[i][1])std::cout << "ERROR: " << tlj[i][0] << " and " << tlj[i][1] << " are not found." << "\n";
        else if (!ques[i][0] && ques[i][1])std::cout << "ERROR: " << tlj[i][0] << " is not found." << "\n";
        else if (ques[i][0] && !ques[i][1])std::cout << "ERROR: " << tlj[i][1] << " is not found." << "\n";
        else
        {
            int flag = 0;
            int a = love[tlj[i][0]], b = love[tlj[i][1]], U = tlj[i][0], V = tlj[i][1];
            if (a > b)std::swap(a, b), flag = 1;
            int LCA = ans[{a, b}];
            if (love[LCA] == a)
            {
                if (flag)std::cout << V << " is an ancestor of " << U << "." << "\n";
                else std::cout << U << " is an ancestor of " << V << "." << "\n";
            }
            else if (love[LCA] == b)
            {
                if (flag)std::cout << U << " is an ancestor of " << V << "." << "\n";
                else std::cout << V << " is an ancestor of " << U << "." << "\n";
            }
            else std::cout << "LCA of " << U << " and " << V << " is " << LCA << "." << "\n";
        }
    }

    return 0;
}