LCA

LCA(Lowest Common Ancestor)는 최소 공통 조상이라고도 불리며

트리에서 두 노드 u와 v를 모두 자손으로 갖는 노드 중 가장 아래에 있는 노드를 구하는 기법입니다.

기본적으로 아래의 과정을 진행하여야 합니다.

1. u보다 v가 더 깊이(depth)가 더 깊을 경우 v를 부모노드로 올린다.

2. 이제 u와 v의 깊이가 같아졌을 경우 u와 v를 같이 부모노드로 올린다.

3. 2번 과정을 u와 v가 같은 노드를 가리킬 때까지 진행한다.

하나하나 부모노드로 올려 진행하였을 때 최악의 경우에는 O(N)의 시간복잡도로 LCA를 구하게 되는데

앞서 배운 DP와 비트마스크 기법을 이용하여

정점의 2^k번째 부모를 부분문제로 저장하여 O(lgN)만에 구할 수 있습니다.

이는 트리 상에서 두 정점의 거리를 빠르게 구하고 싶을 때 사용할 수도 있으며

이외에도 트리에서 문제를 푸는 아이디어의 일부가 되는 기법입니다.

기본 문제

11437번: LCA

11438번: LCA 2

1761번: 정점들의 거리