최소 공통 조상 (LCA)

문제 설명

루트가 있는 트리에서 두 노드의 최소 공통 조상(Lowest Common Ancestor)을 구하세요.

입력 형식

첫 줄: 노드 수 N

다음 N-1줄: 부모 자식

다음 줄: 쿼리 수 Q

다음 Q줄: 두 노드 a b

출력 형식

각 쿼리에 대한 LCA

알고리즘

• 희소 테이블(Sparse Table) 사용
• 전처리: O(N log N)
• 쿼리: O(log N)