노드 수가 최대 100,000개까지 늘어난 LCA 문제다. 이전 문제랑 조건은 거의 똑같고, 루트는 1번, M개의 쿼리에 대해 LCA를 출력하면 된다. 앞 문제랑 거의 구조는 같지만, 입출력이 병목이 될 수 있어서 scanf/printf 대신 fread/fwrite 같은 걸 써야 하나 고민했다. 하지만 scanf/printf도 ios::sync_with_stdio(false)가 없는 C에선 꽤 빠르게 작동한다. 그래서 우선은 그대로 뒀다. 대신 인접 리스트는 배열 대신 vector처럼 동적 크기로 직접 관리했다. 배열은 공간 낭비가 심하니까. 또 하나는 depth랑 희소 배열을 전역 변수로 재사용하면서 메모리 관리도 신경 썼다. 풀이 방식 - DFS로 깊이와 바로 위 부모 채움 - 희소 배열 (parent[i][k] → i의 2^k번째 부모) 구성 - 두 노드의 깊이를 맞춰주고, 동시에 올라가면서 공통 조상을 찾음

#include 
#include 
#include 

#define MAXN 100001
#define LOGN 17

int N, M;
int depth[MAXN];
int parent[MAXN][LOGN];
int visited[MAXN];

typedef struct {
    int to;
    int next;
} Edge;

Edge edges[MAXN * 2];
int head[MAXN], edgeCount = 0;

void addEdge(int u, int v) {
    edges[edgeCount].to = v;
    edges[edgeCount].next = head[u];
    head[u] = edgeCount++;
}

void dfs(int node, int p, int d) {
    visited[node] = 1;
    depth[node] = d;
    parent[node][0] = p;

    for (int i = head[node]; i != -1; i = edges[i].next) {
        int next = edges[i].to;
        if (!visited[next]) {
            dfs(next, node, d + 1);
        }
    }
}

void preprocess() {
    for (int j = 1; j < LOGN; j++) {
        for (int i = 1; i <= N; i++) {
            if (parent[i][j - 1] != 0)
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) {
        int temp = a;
        a = b;
        b = temp;
    }

    int diff = depth[a] - depth[b];
    for (int i = 0; i < LOGN; i++) {
        if ((diff >> i) & 1)
            a = parent[a][i];
    }

    if (a == b) return a;

    for (int i = LOGN - 1; i >= 0; i--) {
        if (parent[a][i] != 0 && parent[a][i] != parent[b][i]) {
            a = parent[a][i];
            b = parent[b][i];
        }
    }

    return parent[a][0];
}

int main() {
    memset(head, -1, sizeof(head));

    scanf("%d", &N);
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }

    dfs(1, 0, 0);
    preprocess();

    scanf("%d", &M);
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", lca(a, b));
    }

    return 0;
}

정리 - 이전 문제랑 로직은 같았지만, 입출력 / 메모리 / 연결 리스트 구현 등 세부적인 부분에서 차이가 생겼다. - Edge 구조체를 만들어서 직접 연결리스트를 구현하니까 메모리도 절약되고, 속도도 빨라졌다. - 트리 문제에서 성능을 올릴 땐 LCA는 물론, 데이터 구조 최적화도 고려해야 한다는 걸 배웠다. 앞 문제에서 배운 Binary Lifting을 그대로 적용했다. 처음에 배열로 인접 리스트 구성했다가 메모리 터져서 구조체로 바꿨다. 트리 문제에서 시간 초과, 메모리 초과 날 땐 알고리즘 말고도 구현 방식부터 체크해야 한다는 걸 느꼈다. 다음엔 이걸 기반으로 다이나믹 트리라든가, 트리 경로 쿼리 같은 문제를 풀어보고 싶다. 계속 트리 문제 몰아서 푸니까 감도 익고 확실히 자신감 붙는 느낌이었다.