최소 공통 조상 찾기

1. 모든 노드에 대한 깊이를 계산한다.
2. 최소 공통조상을 찾을 두 노드를 확인한다.
1. 먼저 두 노드의 깊이가 동일하도록 거슬러 올라간다.
2. 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다.
3. 모든 LCA(a,b)연산에 대하여 2번의 과정을 반복한다.

import sys
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline

n = int(input())

# initalize
parent = [0] * (n+1)
d = [0] * (n+1)
c = [0] * (n+1)
graph = [[] for _ in range(n+1)]

## make graph
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

## make parent tree    
def dfs(x, depth):
    c[x]=True
    d[x]=depth
    for y in graph[x]:
        if c[y]:
            continue
        parent[y]=x
        dfs(y,depth+1)

# parent =      [0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 7, 7, 11]
# d = [0, 0, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4]

# A와 B의 최소 공통 조상을 찾는 함수
def lca(a, b):
    # 깊이가 동일하도록
    while d[a] != d[b]:
        if d[a] > d[b]:
            a = parent[a]
        else:
            b = parent[b]
    
    # 노드가 같아지도록
    while a != b:
        a= parent[a]
        b= parent[b]
    return a

dfs(1, 0) #루트 노드는 1번

t = int(input())

for i in range(t):
    a, b = map(int, input().split())
    print(lca(a, b))

다음과 같이 dfs를 이용해 lca문제를 풀 수 있으나 시간초과 판정이 난다면 부모를 찾으러 올라갈때 2의 제곱만큼 거슬러 올라갈 수 있도록 해야한다

다이나믹 프로그래밍을 이용해 시간 복잡도를 개선할 수 있으며, 세그먼트 트리를 이용하는 방법도 존재한다.

매 쿼리마다 부모를 거슬러 올라가기 위해0(logN)의 복잡도가 필요하다.

따라서 모든 쿼리를 처리할 떄의 시간 복잡도는 0(MlogN)이다.

import sys
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline
LOG = 21

n = int(input())

# initalize
parent = [[0] * LOG for _ in range(n+1)]
d = [0] * (n+1)
c = [0] * (n+1)
graph = [[] for _ in range(n+1)]

## make graph
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

## make parent tree    
def dfs(x, depth):
    c[x]=True
    d[x]=depth
    for y in graph[x]:
        if c[y]:
            continue
        parent[y][0]=x
        dfs(y,depth+1)



def set_parent():
    dfs(1, 0)
    for i in range(1, LOG):
        for j in range(1, n + 1):
            parent[j][i] = parent[parent[j][i-1]][i-1]

set_parent()

# parent = [
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
# [4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [5, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [5, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [7, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [7, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [11, 5, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# ]

# d = [0, 0, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4]

# A와 B의 최소 공통 조상을 찾는 함수
def lca(a, b):
    # b가 더 깊도록
    if d[a] > d[b]:
        a, b = b, a
    # 깊이 통일
    for i in range(LOG-1, -1, -1):
        if d[b] - d[a] >= (1 << i):
            b = parent[b][i]
    
    # 부모가 같아지도록
    if a == b:
        return a
    for i in range(LOG -1, -1, -1):
        #조상을 향해 거슬러 올라가기
        if parent[a][i] != parent[b][i]:
            a = parent[a][i]
            b = parent[b][i]
    # 이후에 부모가 찾고자 하는 조상
    return parent[a][0]

t = int(input())

for i in range(t):
    a, b = map(int, input().split())
    print(lca(a, b))