POJ - 1330 Nearest Common Ancestors LCA-樹上倍增

題目連結：傳送門

題意：求兩點的LCA

樹上倍增LCA即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 1e4+50;

int in[MAXN], Next[MAXN], ver[MAXN], head[MAXN], dep[MAXN];
int f[MAXN][110];
int n, tot, m;

void add(int x, int y){
    ver[++tot] = y; Next[tot] = head[x]; head[x] = tot;
}

void init(int n){
    tot = 0;
    m = (int)(log2(n));
    for(int i = 0; i <= n; i++) {
        in[i] = Next[i] = ver[i] = head[i] = dep[i] = 0;
    }
    memset(f, 0, sizeof(f));
}

void dfs(int u){
    for(int i = 0; i < m; i++){
        if(f[u][i - 1]) f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for(int i = head[u]; i; i = Next[i]){
        int to = ver[i];
        if(to != f[u][0]){
            f[to][0] = u;
            dep[to] = dep[u] + 1;
            dfs(to);
        }
    }
}

int getlca(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);
    int cnt = dep[x] - dep[y];
    for(int i = 0; i < m; i++)
        if((1<<i) & cnt) x = f[x][i];
    if(x == y) return x;
    for(int i = m; i >= 0; i--){
        if(f[x][i] != f[y][i]){
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        init(n);
        for(int i = 1; i < n; i++){
            int u, v;
            scanf("%d%d", &u, &v);
            in[v]++;
            add(u, v);
        }
        int id = 0;
        for(int i = 1; i <= n; i++){
            if(!in[i]){
                id = i;
                break;
            }
        }
        //cout << '*' << id << endl;
        dfs(id);
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", getlca(a, b));
    }
    return 0;
}