[백준]3584번/ 가장 가까운 공통 조상

1. 각 노드에 대해 부모 노드를 구한다.
2. 두 노드 중 하나에서 루트 노드까지의 경로를 구한다.
3. 두 번째 노드에서 루트 노드까지 이동하면서, 이 노드가 첫 번째 노드의 경로에 속하는지 확인한다.
4. 만약 속한다면, 그 노드가 가장 가까운 공통 조상이 된다.

📖문제
https://www.acmicpc.net/problem/3584

import sys


t=int(sys.stdin.readline().rstrip())

def solution():
    n = int(sys.stdin.readline().rstrip())
    tree=[0 for _ in range(n+1)]

    for _ in range(n-1):
        a,b=map(int,sys.stdin.readline().rsplit())
        tree[b]=a

    c1,c2=map(int,sys.stdin.readline().rsplit())

    p1=[c1]
    while tree[c1] != 0:
        c1 = tree[c1]
        p1.append(c1)

    p2=[c2]
    while tree[c2] != 0:
        c2 = tree[c2]
        p2.append(c2)

    for i in p1:
        if i in p2:
            print(i)
            break

for _ in range(t):
    solution()