跳步祖宗数组 fa ： fa [ i ] [ 20 ] 表示从当前位置向上跳 2^ j 次方步后所在的点的代号。

深度数组 depth[ i ] : 表示当前的点的深度。（用于比较两点位置。

跳步祖宗数组需要预处理：（dfs

for(int i = 1; i <= n; i ++)
{
    if(!st[i])  // 挨个， 防止有不连通的块没有遍历到；
    {
        depth[i] = 1;
        dfs(i);
    }
}

void dfs(int x)
{
    st[x] = true;
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if(b[y]) continue;
        st[y] = true;
        depth[y] = dep[x] + 1;
        f[y][0] = x; // y 的 2 的 0 次方个祖宗是 x
        dfs(y);
    }
    return;
}

对于跳步祖宗数组 ：

递推关系： fa[ i ] [ j ] = fa [ f [ i ] [ j - 1] ]  [ j - 1] ; ( i 的第 2 ^ j  次方个祖宗 是  i 的第 2 ^ j - 1 个祖宗的 第 2 ^ j - 1 个祖宗。

例题： [NOIP2013]货车运输 - 题库 - 计蒜客 (jisuanke.com)

lca 部分：

lca(int x, int y)
{
    if(find(x) != find(y)) return -1; // 不连通。
    int ans = inf;
    if(depth[x] > depth[y]) swap(x, y); // 先处理更深的。
    for(int i = 20; i >= 0; i -- ) // 从远处开始跳。
    {
        if(depth[fa[y][i]] >= depth[x])
        {
            ans = min(ans, min[y][i]);
            y = fa[y][i];
        }
    }
    if(x == y) return ans;
    for(int i = 20; i >= 0; i -- )
    {
        if(fa[x][y] != fa[y][i]) // 同时跳。
        {
            ans = min(ans, min(minn[x][i], minn[y][i]));
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return ans;
}

ac：

int h[N], ne[N], e[N], idx;
int w[N];
int f[N];
int fa[N];
int depth[N];

struct edges
{
    int x, y, w;
}edge[N];

bool cmp(const edges &a, const edges &b)
{
    return a.w > b.w;
}

void kruskal()
{
    sort(edge + 1, edge + 1 + m, cmp);
    for(int i = 1; i <= n; i ++)
    f[i] = i;
    for(int i = 1; i <= m; i ++)
    {
        int xx = edge[i].x, yy = edge[i].y;
        int ww = edge[i].w;
        if(find(xx) != find(yy))
        {
            f[find(xx)] = find(yy);
            add(xx, yy, ww);
            add(yy, xx, ww);
        }
    }
    return;
}

void dfs(int x)
{
    st[x] = true;
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if(st[y]) continue;
        st[y] = true;
        depth[y] = depth[x] + 1;
        fa[y][0] = x;
        minn[y][0] = w[i];
        dfs(y);
    }
    return;
}

lca(int x, int y)
{
    if(find(x) != find(y)) return -1; // 不连通。
    int ans = inf;
    if(depth[x] > depth[y]) swap(x, y); // 先处理更深的。
    for(int i = 20; i >= 0; i -- ) // 从远处开始跳。
    {
        if(depth[fa[y][i]] >= depth[x])
        {
            ans = min(ans, min[y][i]);
            y = fa[y][i];
        }
    }
    if(x == y) return ans;
    for(int i = 20; i >= 0; i -- )
    {
        if(fa[x][y] != fa[y][i]) // 同时跳。
        {
            ans = min(ans, min(minn[x][i], minn[y][i]));
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return ans;
}

void solve()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= m; i ++)
    {
        scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].w);
    }
    kruskal();
    for(int i = 1; i <= n; i ++)
    {
        if(!st[i])
        {
            depth[i] = 1;
            dfs(i);
        }
    }
    for(int i = 1; i <= 20; i ++)
    for(int j = 1; j <= n; j ++)
    {
        fa[j][i] = fa[fa[j][i - 1]][i - 1];
        minn[j][i] = min(min[[j][i - 1]][i - 1], min[j][i]);
    }
    cin >> q;
    while(q --)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", lca(x, y));
    }
return;
}