【ACWing】1644. 二叉树中的最低公共祖先

题目地址：

https://www.acwing.com/problem/content/description/1646/

树中两个结点 U U U和 V V V的最低公共祖先（LCA）是指同时具有 U U U和 V V V作为后代的最深结点。给定二叉树中的任何两个结点，请你找到它们的LCA。

输入格式：
第一行包含两个整数 M M M和 N N N，分别表示询问结点对数以及二叉树中的结点数量。接下来两行，每行包含 N N N个不同的整数，分别表示二叉树的中序和前序遍历。保证二叉树可由给定遍历序列唯一确定。接下来 M M M行，每行包含两个整数 U U U和 V V 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没有在二叉树中找到，则输出ERROR: U is not found.或ERROR: V is not found.或ERROR: U and V are not found.。

数据范围：
1 ≤ M ≤ 1000 1≤M≤1000 1≤M≤1000
1 ≤ N ≤ 10000 1≤N≤10000 1≤N≤10000

先根据中序遍历和先序遍历把树递归构造出来，接着用倍增法做预处理来求最近公共祖先即可，参考https://blog.csdn.net/qq_46105170/article/details/116217633。节点值有负数，需要做离散化。代码如下：

#include 
#include 
#include 
#include 
using namespace std;

const int N = 1e4 + 10;
int n, m;
int root, chd[N][2];
int pre[N], in[N], map[N];
int c[N];
int dep[N], f[N][15];
int q[N];

// 求x离散化之后的编号
int get(int x) {
  int l = 1, r = n;
  while (l < r) {
    int mid = l + (r - l + 1 >> 1);
    if (x >= c[mid]) l = mid;
    else r = mid - 1;
  }

  if (c[l] != x) return -1;
  return l;
}

// 递归建树
int dfs(int pl, int pr, int il, int ir) {
  if (pl > pr) return 0;
  int u = pre[pl], lc = map[u] - il, rc = ir - map[u];
  chd[u][0] = dfs(pl + 1, pl + lc, il, map[u] - 1);
  chd[u][1] = dfs(pl + lc + 1, pr, map[u] + 1, ir);
  return u;
}

void bfs() {
  memset(dep, -1, sizeof dep);
  dep[root] = 0;
  int hh = 0, tt = 0;
  q[tt++] = root;
  while (hh < tt) {
    int t = q[hh++];
    for (int i = 0; i <= 1; i++) {
      int v = chd[t][i];
      if (v && dep[v] == -1) {
        dep[v] = dep[t] + 1;
        f[v][0] = t;
        for (int k = 1; 1 << k <= dep[v]; k++)
          f[v][k] = f[f[v][k - 1]][k - 1];
        
        q[tt++] = v;
      }
    }
  }
}

int lca(int a, int b) {
  if (dep[a] < dep[b]) swap(a, b);
  for (int k = 0, diff = dep[a] - dep[b]; 1 << k <= diff; k++)
    if (diff >> k & 1) a = f[a][k];
  
  if (a == b) return a;

  for (int k = log2(dep[a]); k >= 0; k--)
    if (f[a][k] != f[b][k])
      a = f[a][k], b = f[b][k];
  
  return f[a][0];
}

int main() {
  scanf("%d%d", &m, &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &in[i]);
    c[i] = in[i];
  }
  for (int i = 1; i <= n; i++) scanf("%d", &pre[i]);
  sort(c + 1, c + n + 1);
  for (int i = 1; i <= n; i++) {
    pre[i] = get(pre[i]), in[i] = get(in[i]);
    map[in[i]] = i;
  }

  root = dfs(1, n, 1, n);
  bfs();

  while (m--) {
    int a, b;
    scanf("%d%d", &a, &b);
    int x = a, y = b;
    a = get(a), b = get(b);
    if (a == -1 && b == -1)
      printf("ERROR: %d and %d are not found.\n", x, y);
    else if (a == -1)
      printf("ERROR: %d is not found.\n", x);
    else if (b == -1)
      printf("ERROR: %d is not found.\n", y);
    else {
      int p = lca(a, b);
      if (p == a) printf("%d is an ancestor of %d.\n", x, y);
      else if (p == b) printf("%d is an ancestor of %d.\n", y, x);
      else printf("LCA of %d and %d is %d.\n", x, y, c[p]);
    }
  }
}

预处理时间复杂度 O ( N log ⁡ N ) O(N\log N) O(NlogN)，每次询问时间复杂度 O ( log ⁡ N ) O(\log N) O(logN)，空间 O ( N log ⁡ N ) O(N\log N) O(NlogN)。