처음에 문제를 잘못 읽어서 입력으로 들어오는 a, b를 union 연산 하라는 줄 알았는데 알고보니 a가 b의 부모 관계였다. 따라서 유니온 파인드의 기본 풀이인 부모를 찾는 과정은 입력 자체로 바로 알 수 있으니 패스.
마지막 줄에 입력된 두 노드에 대하여 가장 가까운 공통 조상을 구하면 되는데, 이 때 먼저 입력된 노드 ta에 대해 부모 경로를 리스트에 담고 이를 tracking_ta
라고 하자.
이후 tb도 자신의 부모 경로를 거슬러 올라가며 중간에 tracking_ta
안에 있는 값과 일치하는 순간이 온다면 그것을 가장 가까운 공통 조상이라고 간주하고 출력하면 된다.
tc=int(input())
for _ in range(tc):
n=int(input())
parent=[0]*(n+1)
for _ in range(n-1):
a,b=map(int,input().split())
parent[b]=a
ta,tb=map(int,input().split())
tracking_ta=[]
# print(parent)
while True:
if ta==0:
break
tracking_ta.append(ta)
ta=parent[ta]
# print(tracking_ta)
# tracking_ta=set(tracking_ta)
while True:
if tb in tracking_ta:
print(tb)
break
tb=parent[tb]
in
메소드의 시간복잡도를 줄이기 위해 tracking_ta의 자료형을 list 대신 set으로 변환할 수 있다 (그러나 list로 두어도 시간초과가 나지는 않았다)