백준 11438 LCA2

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

LCA는 Lowest Common Ancestor로 최소공통조상을 찾는 알고리즘이다.
두 노드의 최소공통조상을 찾는 방법은
1. 두 노드의 높이를 맞춘다.
2. 노드를 올려보면서 부모가 같은지 확인한다.
이 두가지를 하면 되는데, 부모를 하나씩 올려가며 찾는 방법은 결국 O(n)이 걸리고 노드의 개수가 많아지면 시간초과가 난다.

그렇기 때문에 부모를 하나씩 올려가며 찾는 방법이 아니라, 1,2,4,8씩 올려가며 찾는 방법이다.

1,2,4,8씩 올려가며 찾는다는 알고리즘을 보고 처음 든 생각은 만약 3이나 5에 위치해 있으면 어떻게 찾을까라는 생각이었다.
하지만 비트연산을 이용하면 문제가 해결된다.

먼저 두 노드의 높이차를 맞춰야 하는데, 예를 들어 두 노드의 높이차이가 12라면, 제일 왼쪽 비트부터 밀면서 8만큼 높이차 조정 + 4만큼 높이차 조정의 연산을 거치면 두 노드의 높이차가 맞춰진다.

만약 부모를 하나씩 찾아간다면 12번 만큼의 연산이 필요했겠지만, 위의 방법은 2번의 연산으로 높이차를 조절할 수 있다.

두 노드의 높이차를 맞췄다면, 위로 올라가면서 최소공통조상을 찾아야 하는데,
이 경우에 왼쪽 비트부터 오른쪽으로 비트를 밀면서 확인하면 다음과 같은 문제가 발생하는데,
만약 최소공통조상까지 거리가 8만큼인데 왼쪽부터 오른쪽으로 비트를 밀면서 16만큼의 거리에 공통조상을 발견했다면, 이는 공통조상이 아니기 때문에 제외해야 한다.
그렇기 때문에 만약 거리가 8이라면, 7만큼 높이를 올리고, 그 후에 부모를 찾으면 된다.

그렇기 때문에 위로 올라가면서 루트 위로 트리를 벗어나는 경우를 제외하면, 두 노드의 부모노드가 같지 않을 때까지 노드를 부모노드로 갱신해주면 된다.

import sys
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline
L = 21
n = int(input())
graph = [[] for i in range(n+1)]
parent = [[0]*L for i in range(n+1)]
d = [-1]*(n+1)
def dfs(x,cnt):
    d[x] = cnt
    for node in graph[x]:
        if d[node] == -1:
            parent[node][0] = x
            dfs(node,cnt+1)
for _ in range(n-1):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)
dfs(1,0)
for j in range(1,L):
    for i in range(1,n+1):
        parent[i][j] = parent[parent[i][j-1]][j-1]
m = int(input())
for _ in range(m):
    u,v = map(int,input().split())
    if d[u] > d[v]:
        u,v = v,u
    for i in range(L-1,-1,-1):
        if d[v]-d[u] >= (1<<i):
            v = parent[v][i]
    if u == v:
        print(u)
        continue
    for i in range(L-1,-1,-1):
       if parent[u][i] != parent[v][i]:
           u = parent[u][i]
           v = parent[v][i]
    print(parent[u][0])