LCA

1. LCA란 무엇인가?

트리에서 두 노드 A와 B의 공통 조상이 여러 개 있을 수 있습니다. 이 중에서 A와 B에 가장 가까운, 즉 두 노드의 깊이가 최대인 조상을 최소 공통 조상이라고 부릅니다.

예를 들어, 다음과 같은 트리를 생각해 봅시다.

         1
       /   \
      2     3
     / \   / \
    4   5 6   7

• 노드 4와 5의 공통 조상은 2와 1이 있지만, 가장 가까운 공통 조상은 2입니다.
• 노드 4와 6의 공통 조상은 1밖에 없으므로, LCA는 1이 됩니다.

---

2. LCA가 필요한 문제 상황

문제 상황에 따라 LCA는 다양한 방식으로 응용될 수 있습니다. 예를 들어:

• 두 노드 사이의 거리 구하기: LCA를 활용하면 두 노드 간의 거리를 쉽게 계산할 수 있습니다.
• 경로 쿼리: 트리 상에서 특정 구간에 대한 정보(최소값, 최대값 등)를 구할 때, LCA를 통해 경로를 분할하여 처리할 수 있습니다.
• 트리의 구조 분석: 두 노드의 조상 관계를 파악하여 트리의 계층 구조나 부모-자식 관계를 이해할 수 있습니다.

---

3. 효율적인 LCA 계산: 이진 리프팅(Binary Lifting)

트리의 크기가 클 때, 각 쿼리마다 단순히 부모 노드를 거슬러 올라가는 방식은 비효율적일 수 있습니다. 이때 사용되는 기법이 바로 이진 리프팅(Binary Lifting) 입니다.

3.1 기본 아이디어

이진 리프팅은 "2의 거듭제곱만큼 점프"하는 방식으로 미리 계산된 정보를 이용합니다.
즉, 각 노드에 대해 다음과 같은 정보를 미리 구해둡니다.

• up[node][k]: 노드 node에서 2^k번 위로 올라간 조상

예를 들어,

• up[node][0]는 노드의 직계 부모,
• up[node][1]은 노드의 부모의 부모 (2번 위),
• up[node][2]는 4번 위,
• ... 이런 식입니다.

3.2 LCA 계산 과정

두 노드 u와 v의 LCA를 구하는 과정은 다음과 같습니다.

1. 높이 맞추기:
   만약 u와 v의 깊이가 다르다면, 깊이가 더 깊은 노드를 이진 리프팅을 사용해 같은 높이로 맞춥니다.

2. 동시에 올라가기:
   두 노드의 높이가 같아지면, 각 노드가 서로 다른 조상에 있을 때까지 가장 큰 점프(즉, 2^k)를 사용해 동시에 위로 올라갑니다.
   만약 어떤 시점에서 up[u][k] != up[v][k]라면, 두 노드를 그만큼 점프시킵니다.

3. 최종 조상 선택:
   두 노드가 바로 자식-부모 관계가 되면, 부모가 바로 LCA가 됩니다.

이 방식은 각 쿼리를 $O(\log N)$ 시간에 처리할 수 있어, 대규모 트리에서도 효율적입니다.

3.3 간단한 예시 코드 (C++)

const int MAX_K = 20;  // 최대 2^20 정도 점프 가능 (노드 수에 따라 조절)
vector<vector<int>> up(n + 1, vector<int>(MAX_K));

// 1. 초기화: up[node][0] = parent[node]
for (int node = 1; node <= n; node++) {
    up[node][0] = parent[node];
}

// 2. 이진 리프팅 테이블 채우기
for (int k = 1; k < MAX_K; k++) {
    for (int node = 1; node <= n; node++) {
        if (up[node][k-1] != -1)
            up[node][k] = up[ up[node][k-1] ][k-1];
        else
            up[node][k] = -1;
    }
}

// 3. LCA 함수 구현 예시
int LCA(int u, int v) {
    if (depth[u] < depth[v])
        swap(u, v);
    // 깊이 맞추기
    for (int k = MAX_K - 1; k >= 0; k--) {
        if (up[u][k] != -1 && depth[ up[u][k] ] >= depth[v])
            u = up[u][k];
    }
    if (u == v)
        return u;
    // 동시에 올라가기
    for (int k = MAX_K - 1; k >= 0; k--) {
        if (up[u][k] != up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }
    }
    return parent[u];
}

이 코드에서는 미리 부모 정보를 기반으로 이진 리프팅 테이블(up)을 구성하고, 이를 사용해 LCA를 효율적으로 계산합니다.

---