LCA_v2

LCA （最近公共祖先）模板整理。

LCA

vector<int>dep(n + 1); 
constexpr int M = 20; // 2 ^ (M - 1) >= n 即可
vector<array<int, M>>f(n + 1); // f[i][j] 表示 i 向上 2^j 层对应的祖宗 
auto dfs = [&](auto &&self, int u, int fa) -> void{
    for(auto &v : adj[u]){
        if(v == fa) continue;
        dep[v] = dep[u] + 1;
        f[v][0] = u;
        for(int i = 1; i < M; i++)
            f[v][i] = f[f[v][i - 1]][i - 1];
        self(self, v, u);
    }
};

auto lca = [&](int x, int y) -> int{
    if(dep[x] < dep[y]) swap(x, y);
    // 保证 x 处于低层
    for(int i = M - 1; i >= 0; i--) if(dep[f[x][i]] >= dep[y]) x = f[x][i];
    // x 向上跳到与 y 同层
    if(x == y) return x;
    // 这种情况说明 y 是 x 的祖宗
    for(int i = M - 1; i >= 0; i--) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    // x, y 同时向上跳，直到跳到即将跳到同一点
    return f[x][0];
};

dep[s] = 1;
dfs(dfs, s, 0);