핵심 정리
| 항목 | 내용 |
|---|---|
| 대상 | 루트가 정해진 트리 |
| 질문 | 두 정점의 가장 가까운 공통 조상 |
| 전처리 | 부모와 깊이 계산 |
| binary lifting | up[k][v]: v의 2^k번째 조상 |
| 질의 | O(log N) |
csharp
int LOG = 18;
int[,] up = new int[LOG, n];
int[] depth = new int[n];구조
LCA는 두 정점을 같은 깊이로 맞춘 뒤, 동시에 위로 올려 가장 가까운 공통 조상을 찾습니다. 부모를 한 칸씩만 따라가면 질의마다 O(N)이 걸릴 수 있으므로, 많은 질의에서는 binary lifting을 씁니다.
text
up[0][v] = v의 부모
up[1][v] = v의 2번째 조상
up[2][v] = v의 4번째 조상전처리는 DFS나 BFS로 깊이와 직계 부모를 채운 뒤, 점화식으로 위쪽 조상을 계산합니다.
csharp
for (int k = 1; k < LOG; k++)
{
for (int v = 0; v < n; v++)
{
up[k, v] = up[k - 1, up[k - 1, v]];
}
}부모가 없는 루트는 자기 자신을 부모로 두면 경계 처리가 단순해집니다.
질의 흐름
먼저 더 깊은 정점을 위로 올려 두 정점의 깊이를 맞춥니다.
csharp
if (depth[a] < depth[b]) (a, b) = (b, a);
int diff = depth[a] - depth[b];
for (int k = 0; k < LOG; k++)
{
if (((diff >> k) & 1) == 1)
{
a = up[k, a];
}
}깊이를 맞춘 뒤 두 정점이 같으면 그 정점이 LCA입니다. 다르면 큰 점프부터 보면서 조상이 달라지는 마지막 지점까지 함께 올립니다.
csharp
if (a == b) return a;
for (int k = LOG - 1; k >= 0; k--)
{
if (up[k, a] == up[k, b]) continue;
a = up[k, a];
b = up[k, b];
}
return up[0, a];주의할 점
LOG는 2^LOG가 정점 수 이상이 되도록 잡아야 합니다. N이 100,000이면 17보다 큰 값이 필요하므로 여유 있게 18 이상을 사용합니다.
LCA는 트리 기준입니다. 일반 그래프에서는 먼저 루트 트리, BFS 트리, DFS 트리처럼 어떤 트리 위의 조상을 묻는지 정의해야 합니다.
참고 링크
1 sources