import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
graph = {i:[] for i in range(1,N+1)}
for i in range(N-1):
x1,x2 = map(int,input().split())
graph[x1].append(x2)
graph[x2].append(x1)
parent = {}
check = {i:0 for i in range(1,N+1)}
depth = {i:0 for i in range(1,N+1)}
check[1] = 1
dq = deque()
dq.append((1,0))
while dq:
x,d = dq.pop()
depth[x] = d
for child in graph[x]:
if check[child]:
continue
check[child] = 1
parent[child] = x
dq.append((child,d+1))
M = int(input())
for i in range(M):
x1,x2 = map(int,input().split())
d1,d2 = depth[x1],depth[x2]
if d1>d2:
for i in range(d1-d2):
x1 = parent[x1]
if d1<d2:
for i in range(d2-d1):
x2 = parent[x2]
for i in range(min(d1,d2)+1):
if x1 == x2:
print(x1)
break
x1 = parent[x1]
x2 = parent[x2]
LCA 2 문제가 있길래 연습삼아 먼저 풀어봤다.
알고리즘은 간단하게 요약하면
1. 루트가 1번이므로, 1번을 기준으로 BFS로 트리를 작성한다.
2. 이때 부모가 누구인지 뿐만 아니라 깊이도 작성한다.
3. 두 노드에 대해서 깊이가 다르면 같은 층까지 일단 올라온다.
4. 한 층씩 올라오면서 같으면 출력한다.
LCS2 를 풀려면 빨리 통과를 해야할텐데, 내 LCA 1을 기준으로도 시간이 오래걸려서 좀 더 수정이 필요할 것 같다.
아마 경로압축 같은걸 신경써야하지 않을까 싶은데 좀 더 고민해봐야겠다.
오늘의 교훈) 시간을 좀 더 단축시켜서 LCA2를 풀어보자