8055 : 최소 공통 조상 (LCA)
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
루트가 $1$번인 트리 구조가 주어집니다. 여러 개의 노드 쌍 $(a, b)$에 대해 그들의 최소 공통 조상(Lowest Common Ancestor, LCA)을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N, Q \le 200{,}000$
• $1 \le p_i < i$
• $1 \le a, b \le N$
[제약 조건]
• $1 \le N, Q \le 200{,}000$
• $1 \le p_i < i$
• $1 \le a, b \le N$
입력 설명
첫째 줄에 노드의 수 $N$과 질의의 수 $Q$가 공백으로 구분되어 주어집니다. ($1 \le N, Q \le 200{,}000$)
둘째 줄에 $2, 3, \dots, N$번 노드의 부모 노드 $p_2, p_3, \dots, p_N$이 공백으로 구분되어 주어집니다. ($1 \le p_i < i$)
다음 $Q$개의 줄에 걸쳐 최소 공통 조상을 구할 두 노드 $a, b$가 공백으로 구분되어 주어집니다. ($1 \le a, b \le N$)
둘째 줄에 $2, 3, \dots, N$번 노드의 부모 노드 $p_2, p_3, \dots, p_N$이 공백으로 구분되어 주어집니다. ($1 \le p_i < i$)
다음 $Q$개의 줄에 걸쳐 최소 공통 조상을 구할 두 노드 $a, b$가 공백으로 구분되어 주어집니다. ($1 \le a, b \le N$)
출력 설명
각 질의에 대해 두 노드의 최소 공통 조상 번호를 한 줄에 하나씩 순서대로 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
1 1 3 3
4 5
2 5
1 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3
1
1도움
이진 도약(Binary Lifting) 기법을 사용해 `up[k][i]` 테이블을 전처리하면 각 쿼리를 $O(\log N)$에 빠르게 해결할 수 있습니다. 전처리 시간 복잡도는 $O(N \log N)$입니다.