最近公共祖先 LCA

#include <iostream>
using namespace std;
 
int const lgmax = 20;
int const nmax = 200000;
int fa[1 + nmax][1 + lgmax];  // 每个节点的祖先的倍增指针数组
int level[1 + nmax];          // 节点深度
 
int lca(int x, int y) {
  if(level[x] < level[y])     // 保证x深度更大
    swap(x, y);
  for(int h = lgmax; 0 <= h; h--)
    if(level[y] + (1 << h) <= level[x])
      x = fa[x][h];           // 减少x深度到和y一样
  if(x == y)                  // 如果重合就是LCA
    return x;
  for(int h = lgmax; 0 <= h; h--)
    if(fa[x][h] != fa[y][h]) {  // 从远的指针开始，如果不同，则follow
      x = fa[x][h];
      y = fa[y][h];
    }
  return fa[x][0];
}
 
int main() {
  int n, q;
  cin >> n >> q;
  for(int i = 2; i <= n; i++)
    cin >> fa[i][0];  // 输入每个节点的父节点, 按边输入则用dfs，也类似
 
  for(int h = 1; h <= lgmax; h++)
    for(int i = 1;i <= n; i++)
      fa[i][h] = fa[fa[i][h - 1]][h - 1];   // 准备倍增指针数组
 
  for(int i = 2; i <= n; i++)
    level[i] = level[fa[i][0]] + 1;   // 计算深度
 
  for(int i = 1;i <= q; i++) {
    int x, y;
    cin >> x >> y;
    cout << lca(x, y) << '\n';
  }
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define MXN 50007
using namespace std;
std::vector<int> v[MXN];
std::vector<int> w[MXN];
 
// fa是倍增指针，cost是对应指针的路径长度，dep是每个结点的深度
int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;
 
// dfs，用来为 lca 算法做准备。接受两个参数：dfs 起始节点和它的父亲节点。
void dfs(int root, int fno) {
  // 初始化：第 2^0 = 1 个祖先就是它的父亲节点，dep 也比父亲节点多 1。
  fa[root][0] = fno;
  dep[root] = dep[fa[root][0]] + 1;
  // 初始化：其他的祖先节点：第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第
  // 2^(i-1) 的祖先节点。
  for (int i = 1; i < 31; ++i) {
    fa[root][i] = fa[fa[root][i - 1]][i - 1];
    cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
  }
  // 遍历子节点来进行 dfs。
  int sz = v[root].size();
  for (int i = 0; i < sz; ++i) {
    if (v[root][i] == fno) continue;
    cost[v[root][i]][0] = w[root][i];
    dfs(v[root][i], root);
  }
}
 
// lca。用倍增算法算取 x 和 y 的 lca 节点。
int lca(int x, int y) {
  // 令 y 比 x 深。
  if (dep[x] > dep[y]) swap(x, y);
  // 令 y 和 x 在一个深度。
  int tmp = dep[y] - dep[x], ans = 0;
  for (int j = 0; tmp; ++j, tmp >>= 1)
    if (tmp & 1) ans += cost[y][j], y = fa[y][j];
  // 如果这个时候 y = x，那么 x，y 就都是它们自己的祖先。
  if (y == x) return ans;
  // 不然的话，找到第一个不是它们共同祖先的两个点，也就是LCA下面一层的两个结点。
  // 这个就是从高位开始依次尝试改变二进制位，如果不导致路径重合，就改变之。
  for (int j = 30; j >= 0 && y != x; --j) {
    if (fa[x][j] != fa[y][j]) {
      ans += cost[x][j] + cost[y][j];
      x = fa[x][j];
      y = fa[y][j];
    }
  }
  // 返回结果。
  ans += cost[x][0] + cost[y][0];
  return ans;
}
 
int main() {
  // 初始化表示祖先的数组 fa，代价 cost 和深度 dep。
  memset(fa, 0, sizeof(fa));
  memset(cost, 0, sizeof(cost));
  memset(dep, 0, sizeof(dep));
  // 读入树：节点数一共有 n 个。
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    scanf("%d %d %d", &a, &b, &c);
    ++a, ++b;
    v[a].push_back(b);
    v[b].push_back(a);
    w[a].push_back(c);
    w[b].push_back(c);
  }
  // 为了计算 lca 而使用 dfs。
  dfs(1, 0);
  // 查询 m 次，每一次查找两个节点的 lca 点。
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d %d", &a, &b);
    ++a, ++b;
    printf("%d\n", lca(a, b));
  }
  return 0;
}