LCA (Lowest Common Ancestor)

LCA(최소공통조상)는 트리에서 두 정점의 가장 가까운 공통 조상을 찾는 문제이다. 트리 관련 알고리즘에서 가장基础的인 개념 중 하나이다.

1. 브루트 포스 방식

가장 간단한 접근법은 직접 위로 올라가며 찾는 것이다. 먼저 각 정점의 깊이(depth)와 부모 정보(fa)를 전처리한다.

알고리즘:

1. 두 정점 u, v 중 더 깊은 정점을 찾는다.
2. 깊은 정점을 부모로 올라가서 깊이를 맞춘다.
3. 두 정점이 같아질 때까지 동시에 부모로 올라간다.

시간 복잡도는 O(n)이지만, 트리가 깊을 경우 비효율적이다.

2. 이진 승법 (Binary Lifting)

브루트 포스를 최적화한 방법으로, 2의 거듭제곱만큼 올라갈 수 있게|pre preprocessing한다.

전처리

ancestor[i][u] 배열을 구성한다. 이는 정점 u의 2ⁱ번째 조상을 저장한다. 해당 조상이 존재하지 않으면 0을 저장한다.

void init(int node, int parent) {
    jump[0][node] = parent;
    depth[node] = depth[parent] + 1;
    
    for (int k = 1; k < LOG; k++) {
        jump[k][node] = jump[k-1][jump[k-1][node]];
    }
    
    for (int child : tree[node]) {
        if (child != parent) {
            init(child, node);
        }
    }
}

LCA 查询

두 정점의 깊이를 맞춘 후, 상위 비트부터而下으로 확인하며 올라간다.

int findLCA(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    
    // 깊이 차이만큼 올라가기
    int diff = depth[a] - depth[b];
    for (int k = 0; k < LOG; k++) {
        if (diff & (1 << k)) {
            a = jump[k][a];
        }
    }
    
    if (a == b) return a;
    
    // 함께 올라가기
    for (int k = LOG - 1; k >= 0; k--) {
        if (jump[k][a] != jump[k][b]) {
            a = jump[k][a];
            b = jump[k][b];
        }
    }
    
    return jump[0][a];
}

전처리 복잡도: O(n log n), 查询 복잡도: O(log n)

3. DFS 순서 + 세그먼트 트리 (RMQ 방식)

DFS 순서에서 구간 내 가장 얕은 정점을 찾는 방식으로 LCA를 구한다.

전처리

void build(int node, int parent) {
    order[++timer] = node;
    dfn[node] = timer;
    depth[node] = depth[parent] + 1;
    
    for (int child : tree[node]) {
        if (child != parent) {
            build(child, node);
            order[++timer] = node;
        }
    }
}

void preprocess() {
    timer = 0;
    build(1, 0);
    
    for (int i = 1; i <= timer; i++) {
        seg[i][0] = order[i];
    }
    
    for (int j = 1; (1 << j) <= timer; j++) {
        for (int i = 1; i + (1 << j) - 1 <= timer; i++) {
            int left = seg[i][j-1];
            int right = seg[i + (1 << (j-1))][j-1];
            seg[i][j] = (depth[left] < depth[right]) ? left : right;
        }
    }
}

查询

int queryRMQ(int l, int r) {
    int len = r - l + 1;
    int k = log2(len);
    int left = seg[l][k];
    int right = seg[r - (1 << k) + 1][k];
    return (depth[left] < depth[right]) ? left : right;
}

int lcaQuery(int a, int b) {
    if (a == b) return a;
    int L = dfn[a];
    int R = dfn[b];
    if (L > R) swap(L, R);
    
    int mid = queryRMQ(L + 1, R);
    return parent[mid];
}

전처리 복잡도: O(n log n), 查询 복잡도: O(1)

4. 응용 문제 풀이

문제 D:加权 경로 합계

두 종류의 가중치를 처리해야 할 때, 각 가중치를 분리해서 관리한다. 첫 번째 가중치는 일반 정수, 두 번째 가权重는 32비트 이상 이동하여 저장한다. 차분 배열을 활용하여 LCA를 경유할 때 가중치를 정확히 계산한다.

문제 F:政党 최대 깊이

각政黨(그룹)별로最深정점을 찾는다. 각 정점부터政黨의最深정점까지의 거리를 계산하여 답을 도출한다.

문제 G:경로 포함 관계

두 경로 사이에 포함 관계가 있는지 판단한다. 다음 조건 중 하나라도 만족하면 두 경로는 서로 포함 관계이다:

• LCA(a, b)가 c에서 d로 가는 경로 위에 있다.
• LCA(c, d)가 a에서 b로 가는 경로 위에 있다.

이를 만족하면 "Y", 아니면 "N"을 출력한다.