2015-team4/lca

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int fa[MAXN][21],dep[MAXN];
vector<int> e[MAXN];
void dfs(int v, int f)
{
    fa[v][0] = f;
    for(int i = 1; i <= 20; i++) fa[v][i] = fa[fa[v][i-1]][i-1];
    for(int i = 0; i < e[v].size(); i++){
        int u = e[v][i];
        if(u == f) continue;
        dep[u] = dep[v] + 1;
        dfs(u, v);
    }
}

int lca(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);
    int d = dep[x] - dep[y];
    for(int i = 0; i <= 20; i++) 
        if(d>>i&1) 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 main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i < n; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, 0);
    int m;
    scanf("%d", &m);
    for(int i = 1; i <= m; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", lca(x, y));
    }
    return 0;
}
}}}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int fa[MAXN][21],dep[MAXN];
vector<int> e[MAXN];
void dfs(int v, int f)
{
    fa[v][0] = f;
    for(int i = 1; i <= 20; i++) fa[v][i] = fa[fa[v][i-1]][i-1];
    for(int i = 0; i < e[v].size(); i++){
        int u = e[v][i];
        if(u == f) continue;
        dep[u] = dep[v] + 1;
        dfs(u, v);
    }
}
int lca(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);
    int d = dep[x] - dep[y];
    for(int i = 0; i <= 20; i++) 
        if(d>>i&1) 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 main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i < n; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, 0);
    int m;
    scanf("%d", &m);
    for(int i = 1; i <= m; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", lca(x, y));
    }
    return 0;
}