최소 공통 조상(LCA)

11438 LCA 2 : https://www.acmicpc.net/problem/11438

LCA

- 서로의 깊이를 맞추거나 서로가 같아지는 정점을 찾을 때, 크게 움직이기 위해서 각 정점의 부모 뿐 아니라 2^k번 째 부모까지 저장하여 하나씩 올라가는 작업을 2^k씩 올라간다.

- DP 정의 : parent[K][V] = V번 정점의 2^k번 째 부모 정점 번호

parent[K][V] = parent[K-1]parent[K-1][V]]

1) par[0][] 셋팅

2) par[][] 모두 값 셋팅

3) a, b높이를 같게 맞춤

4) a, b의 최소 공통 조상을 찾아 binary search

5) a==b 이면 노드 자체가 조상. 그 외 a != b 이면 바로 위 조상(par[0][a])

#include <cstdio>

#include <vector>

#include <queue>

using namespace std;

#define KMAX 17 // 2^17 = 131072

int N, M;

vector <int> adj[100001];

queue <int> que;

int depth[100001]; //visit 정보

int par[KMAX + 1][100001];

int main()

{

    scanf("%d", &N);

    for (int i = 0; i <= N; i++)

    { //초기화

        depth[i] = -1;

        adj[i].clear();

        for (int k = 0; k<KMAX + 1; k++) par[k][i] = 0;

    }

    for (int i = 1; i<N; i++)

    {

        int from, to;

        scanf("%d %d", &from, &to);

        adj[from].push_back(to);

        adj[to].push_back(from);

    }

    

    // 트리 만들기

    depth[1] = 0;

    par[0][1] = 1;

    que.push(1);

    while (!que.empty())

    {

        int node = que.front(); que.pop();

        int len = adj[node].size();

        for (int i = 0; i<len; i++) // par[0][] 업데이트

        {

            int nnode = adj[node][i];

            if (depth[nnode] == -1) //노드 방문안했으면,

            {

                par[0][nnode] = node; //nnode의 부모는 node

                depth[nnode] = depth[node] + 1; // depth 갱신

                que.push(nnode);

            }

        }

    }

    

    // make sparse table : 나머지 par[][] 업데이트

    for (int k = 1; k<KMAX + 1; k++)

    {

        for (int n = 1; n <= N; n++)

        {

            // n의 2^k번째 조상은 n의 2^(k-1)번째 조상의 2^(k-1)번째 조상.

            // 2^k = 2^(k-1) + 2^(k-1)

            par[k][n] = par[k - 1][par[k - 1][n]]; // 점화식*****

        }

    }

    

    scanf("%d", &M);

    for (int i = 0, a, b; i<M; i++)

    {

        scanf("%d %d", &a, &b);

        

        //a의 높이를 b와 맞춘다.

        if (depth[a] < depth[b])

        {

            for (int k = KMAX; k >= 0; k--)

            {

                if (a != b && depth[par[k][b]] >= depth[a]) b = par[k][b];

            }

        }

        else if (depth[a] > depth[b])

        {

            for (int k = KMAX; k >= 0; k--)

            {

                if (a != b && depth[par[k][a]] >= depth[b]) a = par[k][a];

            }

        }

        

        int ans;

        

        //유사 binary search

        for (int k = KMAX; k >= 0; k--)

        {

            if (a != b && par[k][a] != par[k][b])

            {

                a = par[k][a];

                b = par[k][b];

            }

        }

        

        // 두 노드가 같다면 -> a는 b의 조상. -> LCA = a

        if (a == b) ans = a;

        else ans = par[0][a]; // 그외, a의 조상 또는 b의 조상

        printf("%d\n", ans);

    }

}