문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

풀이

이 문제는 최소 공통 조상 유형으로 처음 만나본 유형이다.
언뜻보면 dfs bfs로 풀면 될 것 같지만 더 간단한 방법으로 풀이가 가능하다.
방법은 다음과 같다.

7 에서 시작하는 조상들을 먼저 구해준다 7 => 6 => 4 => 8
16 에서 시작하는 조상들을 구해준다 16 => 10 => 4 => 8

여기서 우리는 4와 8이 공통 조상임을 알 수 있다.
8은 루트노드임으로 더이상 조상이 없음도 알 수 있다.

=> 공통의 조상의 첫번째 노드가 뭔지 구해주면 된다.

---

X의 부모 : 로직 설명을 먼저 하자면 들어오는 값들을 입력 받는데 i번째 값의 부모들을 입력받는다
A,B의 부모: 부모들을 입력 받는다. X의 부모를 통해 그 값이 루트노드에 갈때까지 모든 값들을 넣어준다.

result : A,B의 부모가 공통조상이 있다면(조건이 무조건 있음) 맨 뒤의 값은 무조건 존재한다. => 하나씩 index를 당겨가며 (--1) 그 값 들이 같은지 확인하고, 틀릴 때까지 result를 당겨온다.

T=int(input())

for _ in range(T):
  N = int(input())
  X의부모 = [0 for _ in range(N+1)]
  for _ in range(N-1):
    s,e = map(int,input().split())
    X의부모[e] = s
  
  A,B = map(int,input().split())
  A의부모들 = [A]
  B의부모들 = [B]

  # 16 => 10 => 4 => 8 
  아이 = A
  while X의부모[아이]>0:
    A의부모들.append(X의부모[아이])
    아이 = X의부모[아이]
  
  아이 = B
  # 7 => 6 => 4 => 8
  while X의부모[아이]>0:
    B의부모들.append(X의부모[아이])
    아이 = X의부모[아이]
  
  # [16,10,4,8]
  # [7,6,4,8]
  # 8부터 함께 노드가 내려가는데 4까지 동일하다 
  # 공통 조상 => 4,8 가까운것은 4

  result = -1
  try :
    while A의부모들[result] == B의부모들[result]:
      result-=1
  except:
    pass
  print(A의부모들[result+1])