문제
노드가 N개 있는 트리가 있다.
1번 노드가 루트라고 가정했을 때 두 노드가 주어지면
두 노드의 가장 가까운 공통 조상(LCA, Lowest Common Ancestor)을 구하는 프로그램을 작성하여라.
* LCA Jump를 사용하는 경우 pypy3 기준 8초 이내
입력
첫 번째 줄에는 노드의 수 N (2 ≤ N ≤ 300,000)가 주어진다.
두 번째 줄부터 N-1개의 줄에는 트리의 각 간선이 연결하는 두 정점의 번호가 주어진다.
N+1번째 줄에는 쿼리의 수 Q (1 ≤ Q ≤ 300,000)가 주어진다.
N+2번째 줄부터 Q개의 줄에는 두 노드 A, B (1 ≤ A ≠ B ≤ N)가 주어진다.
출력
Q개의 줄에 걸쳐 두 노드의 LCA를 출력한다.
예제
5
1 2
2 3
3 4
2 5
4
1 2
3 5
4 5
3 4
1
2
2
3
힌트
태그
로그인해야 코드를 작성할 수 있어요.