모든 노드마다 나가는 간선이 반드시 1개인 그래프에서 S → E의 탐색을 $O(logN)$ 시간복잡도로 가능하게 한다.

아이디어는 나가는 간선이 반드시 1개라면 트리와도 유사하기 때문(cycle 발생할 수 있어 트리는 아님)에 그 특징을 이용할 수 있다. → LCA를 구하기 위해 전처리 배열을 DP로 만드는 것으로 해결 가능.

문제 및 풀이

개미 (https://www.acmicpc.net/problem/14942)

1번 노드를 root로 하는 트리를 만들 수 있다. 최단 경로가 정해지므로, 희소 배열을 통해 중간에 멈추는 노드까지의 거리를 $O(logN)$으로 구할 수 있다.

• [Code]