LCA最近公共祖先

概述

LCA（Lowest Common Ancestor，最近公共祖先）是树结构中常用的一个问题，指的是树中两个节点的最低共同祖先节点。LCA树链抛分法和倍增法，我们这里讲述倍增法，倍增法是一种高效解决LCA问题的算法之一，通过预处理和动态规划的方式，可以在较快的时间内回答多次LCA查询。

算法步骤

1. 预处理： 算法首先对树进行预处理，计算每个节点的深度和其与2的幂次方祖先的关系。

2. 构建倍增表： 通过构建一个称为倍增表的数据结构，记录每个节点跳跃2^k步后的祖先节点。这样，我们就能够在O(log N)的时间内找到一个节点的第k个祖先。

3. 查询： 对于给定的两个节点u和v，首先确定它们的深度，然后将深度较大的节点跳跃到与深度较小的节点相同深度。接着，同时向上跳跃两个节点，直到找到它们的最近公共祖先。在跳跃的过程中，通过倍增表的信息加速查询。

复杂度

LCA倍增法的时间复杂度是O(N log N)的预处理时间加上O(log N)的查询时间，其中N是树中节点的数量。这种方法在多次查询LCA的情况下非常高效，因为预处理的成本被分摊到了多个查询中。

这个算法在解决树上的LCA问题时，提供了一种有效的方法，尤其适用于需要频繁查询LCA的情况，例如在树上进行大量的图论算法或树算法时。

解释

预处理

对于预处理，我们的递推公式为$$f[i][j] = f[f[i][j-1]][j-1]$$ $f[i][j]$代表从i开始，走$2^j$步到达的点。所以我们要想求出来，可以把$2^j$分为两个$2^{j-1}$的部分。

代入进树：
$$f[x][i] = f[f[x][i-1]][i-1]$$
从节点x往上跳$2^i$的点。

查询结果

对于lca,普遍情况我们查询到的结果并不是他们的最近公共祖先，而是最近公祖先的下一层，为什么不能直接查询到lca的公共祖先，因为在倍增当中，我们可能会出现查询到了公共祖先，但是不是最近的，所以我们转换思路，我们如果查询到同一个点，就代表不成立，缩短重新进行查询，这样就可以避免我们查询到非最近的公共祖先。

封装模板

基础封装，无权图,注意点只能是$1 - n$ ，如果不是则需要离散化。

struct LCA {
    int n;
    vector<vector<int> > h,f;//存图，从i开始向上走2^j步到的点
    vector<int> dep,lg;
    LCA(int n) {
        this->n = n;
        h.resize(n + 1);
        f.resize(n + 1, vector<int>(30));
        dep.resize(n + 1);
        lg.resize(n + 1);
        for(int i=1;i<=n;++i)
            lg[i] = lg[i-1] + (1 << lg[i-1] == i);
    }
    void add(int x, int y) { // 建立双向边
        h[x].push_back(y);
        h[y].push_back(x);
    }
    void dfs(int x, int fa) {
        f[x][0] = fa; // 储存 x 的父节点
        dep[x] = dep[fa] + 1;
        for (int i = 1; i <= lg[dep[x]]; i++) {
            f[x][i] = f[f[x][i - 1]][i - 1];
        }
        for (auto y : h[x]) {
            if (y == fa) continue;
            dfs(y, x);
        }
    }
    int lca(int x, int y) {
        if (dep[x] < dep[y]) swap(x, y);//保证x更深
        while (dep[x] > dep[y]) {
            x = f[x][lg[dep[x] - dep[y]] - 1];
        }
        if (x == y) return x;
        for (int k = lg[dep[x]] - 1; k >= 0; k--) {
            if (f[x][k] == f[y][k]) continue;
            x = f[x][k];
            y = f[y][k];
        }
        return f[x][0];
    }
    int clac(int x, int y) { // 倍增查询两点间距离
        return dep[x] + dep[y] - 2 * dep[lca(x, y)];
    }
    void work(int root = 1) { // 在此初始化
        dfs(root, 0);
    }
};