模板 - 图论 - 最近公共祖先 - 倍增算法 - LCA

注意这里不能再传p=-1了，要传p=0进去。附送一个求两点间路径长度的log的算法，假如边带权，则把dep换成根到该点的路径和即可。

const int MAXN = 100000;
vector <int> G[MAXN + 5];
int dep[MAXN + 5], fa[MAXN + 5][20 + 1];

void dfs(int u, int p) {
    dep[u] = dep[p] + 1;
    fa[u][0] = p;
    for (int i = 1; i <= 20; i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(auto &v : G[u]) {
        if(v == p)
            continue;
        dfs(v, u);
    }
}

int LCA(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--)
        if (dep[x] - (1 << i) >= dep[y])
            x = fa[x][i];
    if (x == y)
        return x;
    for (int i = 20; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int dis(int x, int y) {
    return dep[x] + dep[y] - 2 * dep[LCA(x, y)];
}

模板 - 图论 - 最近公共祖先 - 倍增算法 - LCA

原文：https://www.cnblogs.com/KisekiPurin2019/p/12316367.html