最近公共祖先

LCA

方法1：向上标记法

时间复杂度：O(n)

方法2：倍增

时间复杂度：预处理：O(nlogn)
LCA复杂度：O(logn)
fa[i][j]表示从i开始，向上走2j步能走到的节点，0 <= j <= logn
depth[i]表示i所在深度，规定根节点深度为1
哨兵：如果从i开始，向上走2j步会跳过根节点，那么fa[i][j] = 0, depth[0] = 0

步骤：

1. 先将两点跳至同一层，即将深度大的j跳至深度低的节点i所在层

二进制凑depth[j] - depth[i]

1. 两个点同时往上跳直至最近公共祖先的下一层

AcWing 1172. 祖孙询问

import java.util.*;
public class Main {
    static final int N = 40010, M = N * 2, P = 16;
    static int[] h = new int[N], e = new int[M], ne = new int[M];
    static int n, idx;
    static int[] depth = new int[N];
    static int[][] f = new int[N][P];
    static int[] q = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        Arrays.fill(h, -1);
        int root = -1;
        for (int i = 1; i <= n; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            if (b == -1) root = a;
            else {
                add(b, a);
                add(a, b);
            }
        }
        bfs(root);
        int query = sc.nextInt();
        while (query-- > 0) {
            int a = sc.nextInt(), b = sc.nextInt();
            int p = lca(a, b);
            if (p == a) System.out.println("1");
            else if (p == b) System.out.println("2");
            else System.out.println("0");
        }
    }
    static void bfs(int root) {
        int hh = 0, tt = 0;
        q[0] = root;
        Arrays.fill(depth, 0x3f3f3f3f);
        depth[0] = 0;
        depth[root] = 1;
        while (hh <= tt) {
            int u = q[hh++];
            for (int i = h[u]; i != -1; i = ne[i]) {
                int j = e[i];
                if (depth[j] > depth[u] + 1) {
                    depth[j] = depth[u] + 1;
                    f[j][0] = u;
                    q[++tt] = j;
                    for (int k = 1; k < P; k++) {
                        f[j][k] = f[f[j][k - 1]][k - 1];
                    }
                }
            }
        }
    }
    static int lca(int a, int b) {
        if (depth[a] < depth[b]) {
            int t = a;
            a = b;
            b = t;
        }
        for (int i = P - 1; i >= 0; i--) {
            if (depth[f[a][i]] >= depth[b])
                a = f[a][i];
        }
        if (a == b) return a;
        for (int i = P - 1; i >= 0; i--) {
            if (f[a][i] != f[b][i]) {
                a = f[a][i];
                b = f[b][i];
            }
        }
        return f[a][0];
    }
    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}

方法3：Tarjan-离线LCA

时间复杂度：O(n + m)
在深度优先搜索时，将所有点分为三大类

• 已经遍历过且回溯过的点，标记为2
• 正在搜索的分支，标记为1
• 还未搜索到的点，标记为0

对于已经遍历且回溯过的点，在函数结束时将其并入其子树所在根节点的集和（并查集）。
对于当前正在搜索的点，处理LCA查询，另一个节点是那些已经被标记为2的节点，他们的公共祖先就是当前点所在分支上的某个点。

:::info 求树上任意两点的距离：预处理每个点到根节点的距离，再结合最近公共祖先
例如：a, b, lca(a, b) = c，dist指每个点到根节点的距离
d[a, b] = dist[a] + dist[b] - 2 * dist[c] ::: AcWing 1171. 距离

import java.util.*;
public class Main {
    static final int N = 10010, M = N * 2;
    static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    static int idx;
    static int[] fa = new int[N];
    static int[] dist = new int[N];
    static int[] res = new int[M];
    static List<int[]>[] list = new ArrayList[M];
    static int n, m;
    static int[] st = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        Arrays.fill(h, -1);
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            add(a, b, c);
            add(b, a, c);
        }
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt(), y = sc.nextInt();
            if (list[x] == null) list[x] = new ArrayList<>();
            if (list[y] == null) list[y] = new ArrayList<>();
            list[x].add(new int[]{y, i});
            list[y].add(new int[]{x, i});
        }
        for (int i = 0; i < N; i++)
            fa[i] = i;
        dfs(1, -1);
        tarjan(1);
        for (int i = 0; i < m; i++)
            System.out.println(res[i]);
    }
    static void dfs(int u, int p) {
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i], c = w[i];
            if (j == p) continue;
            dist[j] = dist[u] + c;
            dfs(j, u);
        }
    }
    static void tarjan(int u) {
        st[u] = 1;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (st[j] == 0) {
                tarjan(j);
                fa[j] = u;
            }
        }
        if (list[u] != null) {
            for (int[] pair : list[u]) {
                int v = pair[0], id = pair[1];
                if (st[v] == 2) {
                    int anc = find(v);
                    res[id] = dist[u] + dist[v] - 2 * dist[anc];
                }
            }
        }
        st[u] = 2;
    }
    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static int find(int x) {
        return fa[x] == x ? x : (fa[x] = find(fa[x]));
    }
}

应用

结合次小生成树

AcWing 356. 次小生成树
可以用LCA快速求出任意两个节点之间的最大权值边

结合树上 差分

AcWing 352. 闇の連鎖

int p = lca(a, b);
diff[a]++;
diff[b]++;
diff[p] -= 2;