3584. 가장 가까운 공통 조상

문제의 중요한 점은 마지막에 주어지는 두 노드가 서로 부모가 될 수 있다는 점입니다. 그러니까 둘다 거슬러 올라갈 때 자기 자신도 포함해서 거슬러 올라가 줘야합니다.

 

import sys
T = int(sys.stdin.readline())
for _ in range(T):
    N=int(sys.stdin.readline())
    p_list=[0 for _ in range(N+1)] 
    for _ in range(N-1):
        p,c=map(int,sys.stdin.readline().split())
        p_list[c]=p                    
    a,b=map(int,sys.stdin.readline().split())
    a_parent=[a]
    b_parent=[b]                               
    while p_list[a]:
        a_parent.append(p_list[a])
        a=p_list[a]
    while p_list[b]:
        b_parent.append(p_list[b])
        b=p_list[b]
    a_level=len(a_parent)-1
    b_level=len(b_parent)-1
    while a_parent[a_level]==b_parent[b_level]:  
        a_level-=1
        b_level-=1
    print(b_parent[b_level+1])

 

한 칸씩 올라가면서 부모 배열에 다 저장 해줍니다. 그리고 뒤에서부터 루트 노드이므로 한칸씩 같이 내려왔을 때 달라지는 점. 그점이 바로 루트노드 한칸 아래 점 입니다.  따라서 한칸 위로 거슬러 올라가주면 됩니다.