최소 공통 조상

어떤 문제를 푸는가

루트가 있는 트리에서 두 정점 \(u, v\)의 최소 공통 조상(LCA) — 둘을 모두
자손으로 갖는 조상 중 가장 깊은 정점 — 을 빠르게 구합니다. 트리에서 두 정점
사이의 경로, 거리, 경로 위 질의 등의 핵심 부품입니다.

트리에서 \(u, v\) 사이의 유일한 경로는 항상 \(u \to \text{LCA} \to v\) 형태이므로,
LCA만 알면 경로 길이는

$$ \text{dist}(u, v) = \text{depth}(u) + \text{depth}(v) - 2\cdot\text{depth}(\text{LCA}) $$

로 즉시 구합니다.

단순 방법과 그 한계

두 정점을 같은 깊이로 맞춘 뒤 함께 한 칸씩 올라가면 LCA를 찾을 수 있지만,
한 번에 \(O(\text{높이})\)가 들어 트리가 길면 질의당 \(O(N)\)입니다. 질의가 많으면
느립니다.

희소 배열 (Binary Lifting)

각 정점의 \(2^k\)번째 조상 을 미리 표로 저장합니다.

$$ up[k][v] = v \text{의 } 2^k \text{번째 조상} $$

점화식은

$$ up[k][v] = up[k-1]\bigl(up[k-1][v]\bigr) $$

"\(2^k\)칸 위 = \(2^{k-1}\)칸 두 번"이라는 단순한 관계입니다. \(up[0][v]\)는 직접
부모입니다. \(k\)는 \(0\)부터 \(\lceil \log_2 N \rceil\)까지 둡니다.

질의 — 두 단계

1. 깊이 맞추기 — 더 깊은 정점을 \(2^k\) 점프들로 끌어올려 두 정점 깊이를
   같게 한다. 깊이 차를 이진수로 보고 켜진 비트만큼 점프.
2. 함께 올라가기 — 두 정점이 달라지는 가장 큰 점프 를 큰 \(k\)부터 시도해
   함께 올린다. 더 못 올라가는 지점 바로 위가 LCA(즉 up[0]).

큰 점프부터 시도하는 이유: LCA 바로 아래까지 최대한 올라가되 LCA를 넘지 않기
위해서입니다.

복잡도

전처리 한 번에 표를 만들어 두면 이후 모든 질의가 \(O(\log N)\)입니다.

다른 접근들

• 오일러 투어 + 희소 테이블(RMQ) — 전처리 \(O(N \log N)\), 질의 \(O(1)\).
• 오프라인 타잔 LCA — 유니온 파인드로 \(O((N+Q)\alpha)\).

대부분의 문제에선 구현이 깔끔한 희소 배열이 표준입니다. 다음 강의에서 구현과
응용을 봅니다.

희소 배열 LCA 구현 (C++)

DFS로 깊이와 부모를 정한 뒤 표를 채웁니다.

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

int n, LOG;
vector<vector<int>> adj, up;     // up[k][v]
vector<int> depth;

void dfs(int v, int p) {
    up[0][v] = p;
    for (int u : adj[v]) {
        if (u == p) continue;
        depth[u] = depth[v] + 1;
        dfs(u, v);
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);       // u가 더 깊게
    int diff = depth[u] - depth[v];
    for (int k = 0; k < LOG; k++)              // 깊이 맞추기
        if (diff & (1 << k)) u = up[k][u];
    if (u == v) return u;                      // 한쪽이 조상이면 끝
    for (int k = LOG - 1; k >= 0; k--)         // 큰 점프부터 함께 올림
        if (up[k][u] != up[k][v]) {
            u = up[k][u]; v = up[k][v];
        }
    return up[0][u];                           // 한 칸 위가 LCA
}

int main() {
    cin >> n;
    LOG = 1; while ((1 << LOG) < n) LOG++;
    adj.assign(n + 1, {});
    up.assign(LOG, vector<int>(n + 1, 0));
    depth.assign(n + 1, 0);
    for (int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b); adj[b].push_back(a);
    }
    depth[1] = 0;
    dfs(1, 1);                                  // 루트의 부모를 자기 자신으로
    for (int k = 1; k < LOG; k++)               // 표 채우기
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];
    // lca(u, v) 호출
}

루트의 부모를 자기 자신(up[0][root] = root)으로 두면 경계에서 점프가
루트에 머물러 안전합니다.

큰 트리에서 DFS 깊이

\(N\)이 수십만이면 재귀 DFS가 스택 오버플로 위험. BFS로 깊이/부모를 정해도
무방합니다(표 구축은 그대로).

흔한 함정

• 표 구축 순서 — up[0](직접 부모)을 먼저 다 채운 뒤 \(k\) 오름차순으로
  나머지를 채워야 합니다. 순서가 어긋나면 표가 깨집니다.
• LOG 크기 — \(2^{LOG} \ge N\)이 되도록. 작으면 깊은 점프를 못 합니다.
• 깊이 맞추기 후 동일 검사 — u == v면 한쪽이 다른 쪽 조상이니 그대로
  반환. 빼먹으면 한 칸 더 올라가 오답.
• 큰 점프부터 — 함께 올라갈 때 k를 내림차순으로. 오름차순이면 LCA를
  지나칩니다.

응용 패턴

• 트리 두 점 사이 거리 — depth[u]+depth[v]-2*depth[lca].
• 경로 위 k번째 정점 / 조상으로 점프 — up 표를 그대로 활용.
• 경로 합/최값 질의 — LCA로 경로를 두 조각으로 나눠 처리(희소 배열에
  추가 정보를 함께 올리거나, HLD로 확장).
• 트리에서 두 점 경로가 어떤 정점/간선을 지나는가 — LCA로 포함 판정.

LCA는 그 자체로도 쓰이지만, 트리 위의 경로 문제를 "조상 점프"로 환원 하는
열쇠라는 점이 더 중요합니다. 희소 배열 한 벌이 거리·조상·경로 질의를 모두
\(O(\log N)\)에 풀어 줍니다.

출제 신호

• 트리에서 "두 정점 \(u, v\) 사이의 거리/경로"를 묻는 질의가 많이
  (\(Q \le 10^5\)) 들어옴 — 경로는 항상 \(u \to \text{lca} \to v\)로 꺾이므로
  거의 모든 트리 경로 질의가 LCA로 분해됩니다.
• "공통 조상", "두 사람이 만나는 가장 가까운 조상", 족보/디렉터리 구조
• "정점 \(u\)의 \(k\)번째 조상" 질의 — LCA의 부품인 희소 배열 그 자체
• 제약 신호: \(N, Q\)가 둘 다 \(10^5\) 이상 — 질의당 \(O(N)\) 단순 타고 오르기
  (\(O(NQ) = 10^{10}\))는 불가능하고, 전처리 \(O(N \log N)\) + 질의 \(O(\log N)\)이
  요구되는 크기입니다. \(N, Q\)가 수천이면 단순 방법도 통과합니다 —
  제약을 보고 구현 무게를 정하세요.

풀이 결정 절차

1. DFS/BFS 한 번으로 depth[v]와 up[0][v] = parent 를 채웁니다.
2. 희소 배열을 만듭니다 — up[k][v] = up[k-1][ up[k-1][v] ],
   \(2^{\text{LOG}} \ge N\)이 되도록 LOG를 잡습니다 (\(N \le 10^5\)면 LOG = 17).
3. 질의 절차 — (a) 깊이를 맞추고, (b) 위에서부터 \(k\)를 줄여 가며 "조상이
   달라지는 동안" 같이 점프, © 마지막에 한 칸 더 올라간 것이 LCA.
4. 거리 질의면 dist(u, v) = depth[u] + depth[v] - 2 * depth[lca],
   간선 가중치가 있으면 depth 대신 루트로부터의 가중 거리를 같이 들고
   다닙니다.

자주 하는 실수

• 깊이 맞추기 생략/순서 실수 — 두 정점의 깊이가 다르면 먼저 깊은 쪽을
  끌어올려야 합니다. 이때 깊이를 맞췄더니 이미 같은 정점이면 그게 답
  — 이 조기 반환을 빼먹으면 아래 루프가 잘못된 답을 냅니다.

LOG = 17
def lca(u, v):
    if depth[u] < depth[v]:
        u, v = v, u
    diff = depth[u] - depth[v]
    for k in range(LOG):
        if diff >> k & 1:
            u = up[k][u]
    if u == v:                    # 한쪽이 다른 쪽의 조상인 경우
        return u
    for k in range(LOG - 1, -1, -1):
        if up[k][u] != up[k][v]:  # "달라지는 동안만" 점프
            u = up[k][u]
            v = up[k][v]
    return up[0][u]               # 마지막 한 칸은 부모 — 이 줄이 답

• 마지막 up[0][u]를 u로 반환 — 루프가 끝난 시점의 \(u, v\)는 LCA의
  바로 아래 자식입니다. 부모 한 칸을 잊으면 항상 한 단계 아래를 답합니다.
• 점프 조건을 ==로 — "조상이 같으면 점프"로 쓰면 LCA를 지나쳐
  루트까지 올라갑니다. 반드시 "다르면 점프"(LCA 직전까지만 접근)입니다.
• 루트의 부모 처리 — up[0][root]를 root 자신(또는 0번 더미)으로
  정의해 두지 않으면 범위 밖 접근이 납니다.
• LOG 부족 — \(2^{\text{LOG}} < N\)이면 깊은 트리에서 끌어올리기가 모자라
  틀립니다. while (1 << LOG) < n: LOG += 1로 계산하는 게 안전합니다.
• 파이썬 재귀 DFS — 일자 트리에서 한도 초과. 반복 DFS/BFS로 depth와
  parent를 채우세요.

연습 방법

사이드바 연습 목록의 순수 LCA 질의 문제로 희소 배열 전처리와 질의 함수를
암기 수준으로 만든 뒤, 두 정점 거리(가중치 합), 경로 위 최댓값(희소 배열에
max를 함께 저장) 순으로 확장하세요. 직접 작은 트리(7~8개 정점)를 그려
질의 함수를 손으로 추적해 보면 "달라지는 동안 점프 + 마지막 한 칸"의
의미가 분명해집니다. 태그된 문제 3문제 이상 해결 시 마스터 처리되어
레이팅 CLASS 보너스에 반영됩니다.