最近公共祖先 LCA

介绍

给定一棵有根树（不一定为binary tree），求两个节点的最近公共祖先？

算法

LCA的思路和ST表比较相似，都是利用了倍增思想，大概流程如下：

预处理：

用dfs预处理出每一个节点 $u$ 的第$1,2,4,8,…,$ 个parent（即，如果从$u$ 开始，往上跳 $1,2,4,8,…,$ 格，是哪个节点）
记录每一个节点的深度(depth)

预处理parent的时候，利用了倍增的思想：

for (int j = 1; j <= lg[d[cur]]; j++) 
    par[cur][j] = par[par[cur][j-1]][j-1];

询问 $u,v$ 的LCA：

先比较 $u,v$ 的深度，将深的那个往上跳（使用倍增来跳），跳到同一深度。
比较一下当前 $u,v$ 是否相等，如果已经相等了就直接返回 $u$。
否则，尝试同时将 $u,v$ 往上跳，从 步幅最大 的开始尝试，如果发现 步幅过大（即 $u,v$ 的第 $j$ 个parent相同），就不跳（防止跳过头了），否则就两者同时往上跳。
最后，$u,v$ 必然不相同，此时再让它们同时往上跳 $1$ 格就是LCA了。

代码

Luogu-P3379-代码

using namespace std;
#include <bits/stdc++.h>
 
const int maxn = 5e5+5;
const int maxm = 1e6+10;

struct Edge {
    int to, nxt;
} edges[maxm];
int head[maxn], ecnt = 1;

void add(int u, int v) {
    Edge e = {v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

int par[maxn][33];  //记录parent
int d[maxn];  //深度
int n,m,s;
int lg[maxn];  //log2预处理

void dfs(int cur, int p) {
    par[cur][0] = p;
    d[cur] = d[p] + 1;
    for (int j = 1; j <= lg[d[cur]]; j++) par[cur][j] = par[par[cur][j-1]][j-1];
    for (int e = head[cur]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        dfs(to, cur);
    }
}

int query(int u, int v) {
    if (d[u] < d[v]) swap(u,v);
    int diff = d[u] - d[v];
    for (int j = 0; (1<<j) <= diff; j++) {
        if (diff & (1<<j)) {
            u = par[u][j];
        }
    }
    if (u == v) return u;
    for (int j = lg[d[u]]; j >= 0; j--) {
        if (par[u][j] != par[v][j]) {  // 不相同就往上跳
            u = par[u][j], v = par[v][j];
        }
    }
    return par[u][0];
}

void init() {
    cin >> n >> m >> s;  // s是树的root
    for (int i = 1; i <= n-1; i++) {
        int u,v; cin >> u >> v;
        add(u,v); add(v,u);
    }
    lg[1] = 0, lg[2] = 1;
    for (int i = 3; i <= 5e5; i++) lg[i] = lg[i>>1] + 1;
}

int main() {
    init();
    dfs(s, 0);

    while (m--) {
        int u,v; cin >> u >> v;
        int a = query(u,v);
        cout << a << "\n";
    }
}

Contents

介绍

算法

预处理：

询问 $u,v$ 的LCA：

代码