LCA(lca = least common ancestor)

LCA(lca = least common ancestor) 최소 공통 조상

어떤 임의의 자연수는 2^x 종류의 합으로 표현이 가능하다.

예를 들어 5는 2^2 + 2^0 이며 11은 2^3 + 2^1 + 2^0 이다.

이 아이디어를 가지고 트리에서 최소 공통 조상(lca)을 빠르게 알 수 있다.

lca를 구할 때 우리는 up[N][L]와 tin[N], tout[N]을 이용하는데

tin은 새로 방문 된 현재 노드의 시간을 기록해 놓으며(0 부터시작)

tout은 서브트리의 방문이 모두 끝난 후 빠져 나가는 시간을 기록한다.

두 배열을 가지고 우리는 upper함수를 만들어 낸다.

upper함수는 u가 v의 조상노드인지 검사를 한다.

만약 u가 v의 조상 노드라면 v보다 먼저 방문되며 나중에 방문이 끝날것임을

이용한다.

u가 v의 조상이 아니거나 v가 u의 조상이 아닐 때는 up배열을 이용한다.

(예를 들어 아래 트리의 10, 14일 경우)

up[u][i]의 의미는 u의 2^i번째 조상을 나타낸다. 여기서 저 처음에 말한

개념이 들어간다.

up[u][0] = prev로 바로 이전에 방문된 노드가 2^0 = 1 번째 조상이고

up[u][1] = up[up[u][0]][0] 의 의미는 조상의 조상을 나타낸다.

up[u][2] = up[up[u][1]][1] 의 의미는 조상의 조상의// 조상의 조상 2^2번째

를 나타낸다.

그럼 get_lca함수를 보면 처음에 if문 두 개를 볼 수 있다.

u가 이미 v의 조상이면 lca는 u

v가 이미 u의 조상이면 lca는 v

이 둘다 아니면 for문을 수행하는데  ex) 10, 14

up[u][i]가 v의 조상이면 if문을 넘어가고 i를 하나 줄인다.

(그림에는 나타나지 않았지만 1번 노드위에 쭈욱 노드들이 연결되어

있다고 가정을 하면 up[u][L-1]은 전체의 원조?의 번호를 담고있을 것이다.)

i가 줄어들다가 i가 3이 된다면 up[10][3]은 2를 담고있을 것이다.

그럼 여기서 2는 14의 lca가 아니므로 if문 안에 내용이 수행된다.

그럼 u는 2가 되며 다음 for문에서 up[2][2] (=1 또는 1 위에 노드가 있다면 ?)가 

14의 조상이니? 라고 물을 것이다. 그림의 트리로는 up[2][2] = 1로 true로

더이상 u의 변화 없이 for문을 마친다.

주의할게 마지막에 반환하는값은 up[u][0]이다. 이것을 잘 봐야한다고 생각하는데

지금 위의 예에서 u = 2이다. up[2][0]은 1로 (10,14)의 lca는 1로 올바른 값이 반환

되었다. 즉 2^3 + 2^0이 결과이다. 

* for문을 들어가기 전에 두 개의 if문을 체크하는데 이 과정이 없다면

(1, 14)의 lca를 구할 때 1위의 어떤 조상노드가 있다면 이 조상노드가 

반환이 되버린다.

 

요렇게 우리는 u,v의 lca를 빠르게 구해낼 수 있다. 

(아래에는 소스코드, 트리 사진, 결과이미지를 첨부)

lca를 구하는 방법으로 segment tree를 이용하는 방법과 아래의 방법이

있는데 사실 둘다 비슷한 방법인데 아래의 방법이 문제를 풀기에 다른 조건이

들어갔을때 대처하기 좋은거 같다. (개인적으로)

..

[-] Collapse

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define mp make_pair
typedef long long ll;
const int N = 200010;
const int L = 20;

int n, m;
int timer;
int tin[N], tout[N], up[N][L];
vector<int> adj[N];

void dfs(int here, int prev){
    tin[here] = timer++; //언제 방문했는지 기록
    up[here][0] = prev;
    for (int i = 1; i < L; i++) {
        //here의 2^i번째 조상을 저장
        up[here][i] = up[up[here][i - 1]][i - 1];
    }

    for (int i = 0; i < adj[here].size(); i++){
        int next = adj[here][i];
        if (next != prev){
            dfs(next, here);
        }
    }
    tout[here] = timer++; //언제 빠져나왔는지 기록
}

bool upper(int u, int v){
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int get_lca(int u, int v){
    if (upper(u, v)) return u; //u가 lca라면
    if (upper(v, u)) return v; //v가 lca라면
    //설명하기 힘든데 모든 경우를 커버할 수 있음..
    for (int i = L - 1; i >= 0; i--){
        if (!upper(up[u][i], v)){
            u = up[u][i]; // up[u][2] == up[up[u][1]][1]
        }
    }
    return up[u][0];
}

void init(){
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++){
        int u, v; scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

int main(){
    freopen("input.txt", "r", stdin);
    init();
    dfs(1, 1);

    for (int node = 1; node <= n; node++){
        printf("node %d:  ", node);
        for (int i = 0; i < L; i++){
            printf("%d ", up[node][i]);
        }
        puts("");
    }
    return 0;
}