방법 A — 이진 트리 상승(binary lifting)
up[v][k] 를 "\(v\)의 \(2^k\)번째 조상"으로 정의합니다. 그러면
$$ \text{up}[v][0] = \text{parent}(v), \qquad
\text{up}[v][k] = \text{up}[\,\text{up}[v][k-1]\,][k-1] $$
즉 "\(2^{k-1}\)칸 올라간 뒤 다시 \(2^{k-1}\)칸" 이 곧 "\(2^k\)칸"입니다. 전처리는
\(O(n \log n)\). 질의는 (1) 두 정점의 깊이를 맞추고, (2) 조상이 갈라지는
경계까지 함께 큰 점프부터 올라간 뒤, (3) 마지막에 부모를 취합니다.
깊이·부모는 재귀 대신 BFS로 채우면 깊은 트리에서도 스택 걱정이 없습니다.
C++
#include <bits/stdc++.h>
using namespace std;
int LOG;
vector<vector<int>> adj, up; // up[v][k] = v의 2^k번째 조상
vector<int> dep;
void build(int n, int root) {
LOG = 1;
while ((1 << LOG) < n) LOG++;
up.assign(n + 1, vector<int>(LOG));
dep.assign(n + 1, 0);
// BFS로 부모(up[*][0])와 깊이 채우기
vector<char> vis(n + 1, 0);
queue<int> q; q.push(root);
vis[root] = 1; up[root][0] = root; // 루트의 부모는 자기 자신(보초)
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) if (!vis[v]) {
vis[v] = 1; dep[v] = dep[u] + 1;
up[v][0] = u; q.push(v);
}
}
// 희소 조상 표
for (int k = 1; k < LOG; k++)
for (int v = 1; v <= n; v++)
up[v][k] = up[ up[v][k-1] ][k-1];
}
int lca(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
int d = dep[a] - dep[b];
for (int k = 0; k < LOG; k++) // 깊이 맞추기
if (d >> k & 1) a = up[a][k];
if (a == b) return a; // 한쪽이 다른 쪽 조상
for (int k = LOG - 1; k >= 0; k--) // 갈라지기 직전까지 함께 점프
if (up[a][k] != up[b][k]) { a = up[a][k]; b = up[b][k]; }
return up[a][0]; // 마지막 한 칸이 LCA
}
Python
import sys
from collections import deque
def build(n, adj, root):
LOG = max(1, n.bit_length())
up = [[root] * LOG for _ in range(n + 1)]
dep = [0] * (n + 1)
vis = [False] * (n + 1)
q = deque([root]); vis[root] = True
while q:
u = q.popleft()
for v in adj[u]:
if not vis[v]:
vis[v] = True
dep[v] = dep[u] + 1
up[v][0] = u
q.append(v)
for k in range(1, LOG):
for v in range(1, n + 1):
up[v][k] = up[up[v][k-1]][k-1]
return up, dep, LOG
def lca(a, b, up, dep, LOG):
if dep[a] < dep[b]:
a, b = b, a
d = dep[a] - dep[b]
for k in range(LOG):
if d >> k & 1:
a = up[a][k]
if a == b:
return a
for k in range(LOG - 1, -1, -1):
if up[a][k] != up[b][k]:
a = up[a][k]; b = up[b][k]
return up[a][0]
위 트리(정점 9개)에서 lca(4,9)=2, lca(7,8)=6, lca(4,7)=1, lca(9,5)=5 로,
1강의 손계산과 일치합니다.
방법 B — 오일러 투어 + 희소 배열 (\(O(1)\) 질의)
트리를 DFS로 돌며 정점을 방문할 때마다 기록하면 길이 \(2n-1\)의 오일러 투어
배열이 나옵니다. 두 정점 \(u, v\)의 첫 등장 위치 사이 구간에서 깊이가 가장
작은 정점이 곧 \(\text{LCA}(u,v)\)입니다. 구간 최소는 희소 배열(sparse
table) 로 전처리 \(O(n \log n)\), 질의 \(O(1)\)에 답합니다.
C++
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<int> euler, dep_e, first_occ; // 투어, 각 위치의 깊이, 첫 등장 위치
void build_euler(int n, int root) {
euler.clear(); dep_e.clear();
first_occ.assign(n + 1, -1);
vector<int> par(n + 1, 0), dep(n + 1, 0), ptr(n + 1, 0), stk;
par[root] = root; stk.push_back(root);
while (!stk.empty()) {
int u = stk.back();
euler.push_back(u); dep_e.push_back(dep[u]); // 방문마다 기록
if (first_occ[u] == -1) first_occ[u] = euler.size() - 1;
bool moved = false;
while (ptr[u] < (int)adj[u].size()) {
int v = adj[u][ptr[u]++];
if (v == par[u]) continue;
par[v] = u; dep[v] = dep[u] + 1;
stk.push_back(v); moved = true; break;
}
if (!moved) stk.pop_back();
}
}
vector<vector<int>> sp; // sp[k][i] = 구간 [i, i+2^k) 에서 깊이 최소인 위치
void build_sparse() {
int L = euler.size(), K = 1;
while ((1 << K) <= L) K++;
sp.assign(K, vector<int>(L));
for (int i = 0; i < L; i++) sp[0][i] = i;
for (int k = 1; k < K; k++)
for (int i = 0; i + (1 << k) <= L; i++) {
int a = sp[k-1][i], b = sp[k-1][i + (1 << (k-1))];
sp[k][i] = (dep_e[a] <= dep_e[b]) ? a : b;
}
}
int lca(int u, int v) {
int l = first_occ[u], r = first_occ[v];
if (l > r) swap(l, r);
int k = 31 - __builtin_clz(r - l + 1);
int a = sp[k][l], b = sp[k][r - (1 << k) + 1];
return euler[(dep_e[a] <= dep_e[b]) ? a : b];
}
Python (오일러 투어)
import sys
def build_euler(n, adj, root):
euler, dep_e = [], []
first = [-1] * (n + 1)
par = [0] * (n + 1); dep = [0] * (n + 1); ptr = [0] * (n + 1)
par[root] = root; stk = [root]
while stk:
u = stk[-1]
euler.append(u); dep_e.append(dep[u])
if first[u] == -1:
first[u] = len(euler) - 1
moved = False
while ptr[u] < len(adj[u]):
v = adj[u][ptr[u]]; ptr[u] += 1
if v == par[u]:
continue
par[v] = u; dep[v] = dep[u] + 1
stk.append(v); moved = True; break
if not moved:
stk.pop()
return euler, dep_e, first
희소 배열은 위 C++과 같은 방식(깊이 최소 위치를 저장)으로 구성하면 되고, 질의는
first[u], first[v] 구간의 최소 깊이 위치를 꺼내 euler[...] 를 답합니다.
같은 예제 트리에서 두 방법의 답은 정확히 일치합니다.
레이팅 미적용
다이아몬드 I
골드 V