Lowest Common Ancestor (LCA) 예제 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, par[14][10001] = {{0}}, depth_arr[10001] = {0};

void bootstrap(void) {

    for (int i = 1; i < 14; i++) {
        for (int j = 1; j <= n; j++)
            par[i][j] = par[i - 1][par[i - 1][j]];
    }

    return;
}
int depth(int idx) {
    if (depth_arr[idx] != 0)
        return depth_arr[idx];
    
    if (idx == 0)
        return 0;
	
    depth_arr[idx] = depth(par[0][idx]) + 1;
    return depth_arr[idx];
}

int lca(int u, int v) {
    if (depth(u) < depth(v))
        swap(u, v);

    for (int i = 13; i >= 0; i--) {
        if (depth(par[i][u]) >= depth(v))
            u = par[i][u];
    }

    if (u == v)
        return u;
    
    for (int i = 13; i >= 0; i--) {
        if (par[i][u] != par[i][v]) {
            u = par[i][u];
            v = par[i][v];
        }
    }

    return par[0][u];
}

int main(void) {
    scanf("%d", &n);

    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        par[0][b] = a;
    }

    bootstrap();

    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d\n", lca(a, b));
    
    return 0;
}

 

 

이런식으로 구현하면 depth를 계산하기 위해 전처리를 할 필요가 없으므로 깔끔하게 구현할수 있다.