백준 3584 - 가장 가까운 공통 조상 (Python)

최소 공통 조상 알고리즘을 사용하면 됩니다.
구하고자 하는 두 수의 각 부모 노드들을 찾아서 배열에 넣어준 다음 서로 다른 숫자가 나올 때 까지 cnt를 늘려가며 탐색하면 됩니다.

전체 코드

import sys

input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    p = [0] * (n + 1)

    for __ in range(n - 1):
        a, b = map(int, input().split())
        p[b] = a

    a, b = map(int, input().split())

    a_list = [0, a]
    b_list = [0, b]

    while p[a]:
        a_list.append(p[a])
        a = p[a]
    while p[b]:
        b_list.append(p[b])
        b = p[b]

    cnt = 1
    
    while a_list[-cnt] == b_list[-cnt]:
        cnt += 1

    print(a_list[-cnt + 1])