6149 : LCA 바이너리 리프팅
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
1번 노드가 루트인 트리에서 대량의 LCA 쿼리가 주어집니다. Sparse Table을 사용한 바이너리 리프팅(Binary Lifting) 기법을 이용해 각 쿼리를 $O(\log N)$에 해결하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
둘째 줄부터 N-1개의 줄에 트리 간선 정보 u, v가 주어집니다.
그 다음 줄에 쿼리의 개수 Q (1 ≤ Q ≤ 100,000)가 주어지고, 이어서 Q개의 줄에 u, v가 주어집니다.
둘째 줄부터 N-1개의 줄에 트리 간선 정보 u, v가 주어집니다.
그 다음 줄에 쿼리의 개수 Q (1 ≤ Q ≤ 100,000)가 주어지고, 이어서 Q개의 줄에 u, v가 주어집니다.
출력 설명
각 쿼리에 대해 u, v의 최소 공통 조상 노드 번호를 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 2
1 3
2 4
2 5
3
4 5
4 3
2 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2
1
2