最小共通祖先の検索

1.すべてのノードの深さを計算します.
2.2つのノードを確認して、最小の共通の祖先を見つけます.
1.最初に2つのノードに遡る深さは同じです.
2.親ノードが同じになるまで、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))