最近公共祖先LCA

最近公共祖先

P3379 【模板】最近公共祖先（LCA）

倍增思想。dp[i][j]表示结点i的距自己长度为2^j的祖先
dp[i][j] = dp[dp[i][j-1]][j-1]

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 5e5+5;
int n, m, s;
vector<int> G[maxn];
int dp[maxn][27];
int fa[maxn], high[maxn];
int lg[maxn];
inline int LCA(int u, int v){
    if (high[u] < high[v])  swap(u, v);
    while (high[u] > high[v])   u = dp[u][lg[high[u]-high[v]]-1];
    if (u==v)   return u;
    for (int k=lg[high[u]]-1; k>=0; k--)    if (dp[u][k] != dp[v][k])
        u = dp[u][k], v = dp[v][k];
    return dp[u][0];
}
void dfs(int x, int y){             // x的父亲结点是y
    fa[x] = y;
    high[x] = high[y] + 1;
    for (int i=0; i<G[x].size(); i++)   if (!high[G[x][i]])
        dfs(G[x][i], x);
    return;
}
inline int read(){
    int x=0;    char ch = getchar();
    while (ch<'0' || ch>'9')    ch = getchar();
    while (ch>='0'&& ch<='9'){
        x = x*10 + ch-'0';
        ch = getchar();
    }
    return x;
}
int main(){
    int x, y, u, v;
    n = read(), m = read(), s = read();
    for (int i=1; i<n; i++){
        x = read(), y = read();
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(s, 0);
    for (int i=1; i<=n; i++)
        lg[i] = lg[i-1] + (1<<lg[i-1] == i);
    for (int j=1; j<=n; j++)    dp[j][0] = fa[j];
    for (int k=1; k<lg[n]; k++){
        for (int j=1; j<=n; j++){
            dp[j][k] = dp[dp[j][k-1]][k-1];
        }
    }
    for (int i=1; i<=m; i++){
        u = read(), v = read();
        printf ("%d\n", LCA(u, v));
    }
    return 0;
}

一个求log2(i)+1的快速方法。

for (int i=1; i<=n; i++)
    lg[i] = lg[i-1] + (1<<lg[i-1] == i);