LCA 문제를 비롯한 여러 문제를 해결하는 데 다음 방법이 널리 쓰입니다.
#전처리
각 정점에 대해 1번째 조상, 2번째 조상, 4번째 조상 등을 미리 계산합시다. 이를 크기가 $n \times \lceil \log n \rceil$인 2차원 배열 up에 저장합시다. up[v][d]에는 정점 $v$에서 거리 $2^d$만큼 떨어진 조상이 저장되며, 그러한 정점이 존재하지 않으면 루트가 저장됩니다.
이러한 전처리는 $2^{d+1}$ 거리에 있는 조상이 $2^d$ 거리에 있는 조상의 $2^d$ 거리에 있는 조상이라는 사실을 이용하여 $O(n \log n)$에 수행할 수 있습니다:
int up[maxn][logn];
void dfs(int v) {
for (int l = 1; l < logn; l++)
up[v][l] = up[up[v][l-1]][l-1];
tin[v] = t++;
for (int u : g[v]) {
up[u][0] = v;
dfs(u);
}
tout[v] = t;
}
전처리는 총 $O(n \log n)$의 시간과 메모리를 차지합니다. up 배열의 크기가 그만큼이고, 각 원소는 상수 시간에 계산되기 때문입니다.
#쿼리
이제 LCA를 찾는 쿼리, 즉 정점 쌍 $(u, v)$가 주어졌다고 합시다:
- 한 정점이 다른 정점의 조상인지 확인합시다. 그렇다면 그 정점이 바로 결과입니다.
- 그렇지 않다면
up배열을 이용해 두 정점 중 하나의 조상을 따라 올라가면서, 아직 다른 정점의 조상이 아닌 정점 중 가장 높은 정점을 찾습니다. 그 바로 다음 정점이 구하려는 LCA입니다.
두 번째 단계에 대해 더 자세히 살펴보겠습니다. $i = \lceil \log n \rceil$로 두고, up[v][i]가 $u$의 조상이 아니게 될 때까지 이 변수를 1씩 줄여 나갑니다. 그렇게 되면 포인터를 $v$의 $2^i$번째 조상으로 옮기고 계속 진행합니다:
int lca(int v, int u) {
if (a(v, u)) return v;
if (a(u, v)) return u;
for (int l = logn-1; l >= 0; l--)
if (!ancestor(up[v][l], u))
v = up[v][l];
return up[v][0];
}
포인터 up[v][i]는 처음에는 트리의 루트이며, 이후 매 반복마다 $2^i$만큼 내려갑니다. 포인터가 lca의 자손이 되면 한 번만 올라가면 충분합니다. $2^i$ 거리를 두 번 점프하는 것은 $2^{i+1}$ 거리를 한 번 점프하는 것과 같고, 그것은 이전 단계에서 이미 할 수 있었기 때문입니다.
임의의 쿼리에 대한 응답은 $O(\log n)$에 동작합니다. 사실상 이진 탐색을 수행하기 때문입니다.
#경로 쿼리
예를 들어 LCA 대신 임의의 경로 위의 최솟값을 묻는 질의가 주어진다고 합시다(모든 간선에는 어떤 수가 적혀 있습니다).
이진 리프팅 방법에서와 같은 전처리를 하되, $2^d$번째 조상의 번호와 함께 해당 경로 위의 최솟값도 저장할 수 있습니다.
$u$에서 $v$까지의 경로상의 최솟값은 $u$에서 $lca(u, v)$까지의 경로상의 최솟값과 $v$에서 $lca(u, v)$까지의 경로상의 최솟값 중 더 작은 값이라는 점에 주목하십시오. 한편, 이 두 최솟값은 각각 LCA까지의 모든 이진 리프팅 구간에서의 최솟값입니다.
int get_min(int v, int u) {
int res = inf;
for (int l = logn-1; l >= 0; l--)
if (!ancestor(up[v][l], u))
v = up[v][l], res = min(res, mn[v][l]);
for (int l = logn-1; l >= 0; l--)
if (!ancestor(up[u][l], v))
u = up[u][l], res = min(res, mn[u][l]);
return min({res, mn[v][0], mn[u][0]})
}
같은 방식으로 경로 위의 합, gcd, 다항식 해시를 비롯한 여러 특이한 함수들도 계산할 수 있지만, 이는 정적인 경우, 즉 갱신이 없는 경우에만 가능합니다. 동적인 경우에는 heavy-light 분해라고 불리는 훨씬 더 복잡한 방법이 있습니다.