LCA (Lowest Common Ancestor)

LCA란, Lowest Common Ancestor 로, 트리에서의 최소 공통 조상이다.

공통 조상은 두 노드에 대해, 두 노드 모두의 자손인 조상 노드들을 의미하며, 그중 깊이가 최대인 것, 즉 가장 아래쪽에 위치한 노드를 두 노드에 대한 최소 공통 조상 이라 한다.

 

기본적인 아이디어는 두 노드에 대해서

1. 두 노드의 깊이가 같도록 하나의 노드를 올려준 후,

2. 두 노드가 같아질 때까지 올려준다.

 

이 연산을 그냥 실행하면, 최악의 경우에 $O(N)$의 시간이 걸릴 수 있다.

이는 Sparse Table 을 사용하여 LCA 연산을 $O(logN)$에 처리할 수 있다. 

 

가장 먼저 dfs 한번을 돌면서 각 노드들의 깊이와, 노드들의 부모를 sparse table 안에 저장한다.

다음, $par[i][j]=par[par[i][j-1]][j-1]$ 의 점화식을 사용하여 sparse table 을 채운다.

 

이제 완성된 sparse table 을 이용하여 위 두 가지의 연산을 빠르게 해야 한다.

Sparse Table 의 많은 사용처 중 하나가 어떤 점에서 앞의 다른 점으로 건너 뛸 때, 이를 O(lgN) 만에 하기 위하여 사용된다. 

지금 LCA에서 한 정점에서 다른 정점들로 건너뛰는 작업들이 필요하기 때문에 sparse table 이 매우 적합하다.

 

1. i=20 ~ 0 까지 반복하며 $dep[par[i][u]]>=dep[v]$ 를 만족하면 계속 u를 올려준다. 이 과정을 반복하면 두 노드의 깊이가 같아지게 된다.

2. i=20 ~ 0 까지 다시 반복하며 $par[i][u]!=par[i][v]$ 를 만족하면 둘다 모두 함께 올려준다. 이 과정을 통해 LCA의 바로 밑 두 노드들을 구할 수 있다.

 

주의해야할 점은 만약 u의 자손들 중 v가 있으면 2번 단계 전에 끝내야 하고, 2번 단계에서는 u가 아니라 par[0][u]가 LCA라는 점이다.

 

시간 복잡도 : $O(logN)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;

int N, Q;
vector<int> adj[MAXN+10];
int par[MAXN+10][25], dep[MAXN+10];

void dfs(int now, int parent, int depth)
{
    par[now][0]=parent;
    dep[now]=depth;
    for(int nxt : adj[now])
    {
        if(nxt==parent) continue;
        dfs(nxt, now, depth+1);
    }
}

int lca(int u, int v)
{
    int i, j;

    if(dep[u]>dep[v]) swap(u, v);
    for(i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) v=par[v][i];
    if(u==v) return u;
    for(i=20; i>=0; i--) if(par[v][i]!=par[u][i]) v=par[v][i], u=par[u][i];
    return par[u][0];
}

int main()
{
    int i, j;

    scanf("%d", &N);
    for(i=1; i<N; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 1, 0);
    for(j=1; j<=20; j++) for(i=1; i<=N; i++) par[i][j]=par[par[i][j-1]][j-1];

    scanf("%d", &Q);
    while(Q--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
}