문제
풀이
최소 공통 조상(LCA, Lowest Common Ancestor)에 대한 문제이다. 찾고자 하는 node의 부모 노드들을 다 넣는다. 그 이후, 맨 뒤 index인 root 노드에서 차례대로 한개씩 내려오면서 다를 때까지 while문을 진행한다.
달라진다면, 그 직전이 바로 가장 깊은 부모 노드이므로 그것을 출력한다.
소스 코드
```python import sys from math import *
testcase = int(sys.stdin.readline())
for _ in range(testcase):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
N = int(sys.stdin.readline())
parent = [0 for _ in range(N+1)]
for i in range(N-1):
a, b = map(int, sys.stdin.readline().split())
parent[b] = a # b의 부모는 a
target_a, target_b = map(int, sys.stdin.readline().split())
a_parent = [target_a]
b_parent = [target_b]
while parent[target_a]: #a의 조상으로 거슬러 올라갔을 때, 0 -> 즉 root 노드일때까지 진행
a_parent.append(parent[target_a])
target_a = parent[target_a]
while parent[target_b]: #b의 조상으로 거슬러 올라갔을 때, 0 -> 즉 root 노드일때까지 진행
b_parent.append(parent[target_b])
target_b = parent[target_b]
a_depth = len(a_parent)-1
b_depth = len(b_parent)-1
while a_parent[a_depth] == b_parent[b_depth]: #루트노트부터 비교해서 부모노드가 같지 않을 때까지
a_depth -= 1
b_depth -= 1
print(a_parent[a_depth+1])
```
