백준 11438 - LCA 2

문제 링크 : https://www.acmicpc.net/problem/11438

 

문제

N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

풀이 과정

https://readytojoin.tistory.com/entry/LCA-%EC%B5%9C%EC%86%8C-%EA%B3%B5%ED%86%B5-%EC%A1%B0%EC%83%81-%EC%B0%BE%EA%B8%B0

LCA - 최소 공통 조상 찾기

https://readytojoin.tistory.com/entry/Sparse-Table-%ED%9D%AC%EC%86%8C-%EB%B0%B0%EC%97%B4

Sparse Table - 희소 배열

 

기본 LCA 로는 구해야 할 노드의 쌍이 많아 시간 초과가 날 수 있으니, 희소 배열을 이용해 정점 이동 횟수를 줄인다.

# 11438. LCA 2 ( PLATINUM 5 )
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

n = int(input().rstrip())
parent = [-1 for _ in range(n+1)]
graph = [[] for _ in range(n+1)]
depth = [0 for _ in range(n+1)]
visited = [0 for _ in range(n+1)]
table = [[-1 for _ in range(100001)] for _ in range(20)]

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

def DFS(now, p, d):
  global parent
  global graph
  global visited
  global depth
  visited[now] = 1
  depth[now] = d

  for next in graph[now]:
    if visited[next] == 0: DFS(next, now, d + 1)

  parent[now] = p

DFS(1, -1, 0)

for i in range(1, n+1):
  table[0][i] = parent[i]

for k in range(1, 20):
  for i in range(1, n+1):
    table[k][i] = table[k-1][table[k-1][i]]

def LCA(a, b):
  global parent
  global graph
  global visited
  global depth
  
  if depth[a] > depth[b]: 
    for i in range(19, -1, -1):
      if (depth[a] - depth[b]) >= (1 << i):
        a = table[i][a]
  elif depth[a] < depth[b]: 
    for i in range(19, -1, -1):
      if (depth[b] - depth[a]) >= (1 << i):
        b = table[i][b]
        
  if a == b: return a
  else:
    for i in range(19, -1, -1):
      if table[i][a] != table[i][b]:
        a = table[i][a]
        b = table[i][b]
    return table[0][a]

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