_
1. 소개
LCA(Lowest Common Ancestor)는 트리에서 두 노드 \(v\)와 \(w\)의 가장 낮은 공통 조상으로, \(v\)와 \(w\)를 모두 자손으로 갖는 노드들 중에서 가장 루트에서 먼 노드를 말한다. Sparse Table을 사용하여 LCA를 \(O(\log N)\)에 구할 수 있다.
위 그림에서 초록색 정점들이 \(x\)와 \(y\)의 공통 조상이며, 그 중에서 진한 초록색 정점이 LCA다.
2. Code
void dfs(int x){
up[x][0] = p[x]; // x에서 2^0(= 1)번 올라가면 p[x](x의 부모 노드)
for(int j=1; j<MAX_K; j++){ // MAX_K = log(N)번 반복
//up[x][j]에 x에서 2^j번 올라간 노드 번호를 저장해준다
up[x][j] = up[up[x][j-1]][j-1];
}
for(int next : gp[x]){
if(next==p[x]) continue; // next가 x의 부모인 경우
p[next] = x;
lv[next] = lv[x]+1; // 다음 노드의 level을 계산해준다
dfs(next);
}
}
int lca(int x, int y){
for(int i=MAX_K-1; i>=0; i--){
// x와 y의 level이 일치할 때까지 level이 높은 노드의 level을 줄인다
if(lv[up[x][i]]>=lv[y]) x = up[x][i];
if(lv[up[y][i]]>=lv[x]) y = up[y][i];
}
if(x==y) return x;
for(int i=MAX_K-1; i>=0; i--){
if(up[x][i]!=up[y][i]){
x = up[x][i];
y = up[y][i];
}
}
return up[x][0];
}