[백준] LCA

https://www.acmicpc.net/problem/11437

11437번: LCA

문제 제목 그대로 LCA 문제입니다. 일반적인 DFS로는 시간초과가 발생할 것 같아서 DP와 결합된 LCA알고리즘을 활용하여 풀이하였습니다. 

 

import sys
from collections import defaultdict
from math import log, ceil

sys.setrecursionlimit(10 ** 6)

# sys.stdin = open("input.txt", "r")


input = sys.stdin.readline


graph = defaultdict(list)

n = int(input())

h = ceil(log(n) / log(2)) + 1

# 각 정점의 깊이
depth = [0] * (n + 1)

# parent[i][j]: i번 노드의 2 ^ j승번째 부모 노드
parent = [
    [0] * (h)
    for _ in range(n + 1)
]

for _ in range(n - 1):
    n1, n2 = tuple(map(int, input().split()))
    graph[n1].append(n2)
    graph[n2].append(n1)


def dfs(cur, d, pa):
    depth[cur] = d
    parent[cur][0] = pa

    for next_node in graph[cur]:
        if next_node != pa and depth[next_node] == 0:
            dfs(next_node, d + 1, cur)


def lca(a, b):
    # 항상 b가 더 깊게
    if depth[a] > depth[b]:
        a, b = b, a

    # 높이 맞추기
    for i in range(h - 1, -1, -1):
        if (1 << i) <= depth[b] - depth[a]:
            b = parent[b][i]

    if a == b:
        return a

    # 최소 공통 부모를 찾는 과정
    for i in range(h - 1, -1, -1):
        if parent[a][i] != parent[b][i]:
            a = parent[a][i]
            b = parent[b][i]

    return parent[a][0]


# 깊이와 부모노드 기록
dfs(1, 1, 0)

# 부모 노드들을 기록한다.
for i in range(1, h):
    for j in range(1, n + 1):
        parent[j][i] = parent[parent[j][i - 1]][i - 1]

m = int(input())

for _ in range(m):
    a, b = tuple(map(int, input().split()))
    print(lca(a, b))