\(\texttt{0x00}\) 개념
루트 트리에서 노드 \(z\)가 노드 \(x\)와 \(y\)의 공통 조상일 때, \(x\)와 \(y\)의 모든 공통 조상 중 깊이가 최대인 노드를 **최소 공통 조상(LCA)**이라 하며 \(\text{LCA}(x,y)\)로 표기합니다.
\(\texttt{0x01}\) 계산 방법
1. 트리 이진 증가
접근법:
상향 표식법을 개선한 방법으로, 매 단계마다 \(2^k\) 레벨 상위 조상으로 이동합니다. \(\text{anc}[u][k]\)를 노드 \(u\)의 \(2^k\) 번째 상위 조상으로 정의하면 다음과 같은 상태 전이 방정식이 성립합니다:
[\text{anc}[u][k] = \text{anc}[\text{anc}[u][k-1]][k-1]]
\(k\) 범위는 \([1, \log_2 n]\)입니다. BFS를 사용해 트리를 레벨 순서로 탐색하며 \(\text{anc}\) 배열을 \(O(n \log n)\)에 초기화합니다.
질의 \((x,y)\) 처리:
- 깊이가 깊은 노드를 상위로 이동시켜 두 노드 깊이를 동일하게 맞춥니다.
- 두 노드가 동일하면 해당 노드를 반환합니다.
- 그렇지 않으면 \(k = \log_2 n \downarrow 0\) 순회하며 공통 조상이 달라지는 최대 \(k\)값을 찾아 동시에 상승시킵니다.
- 최종적으로 두 노드의 직계 부모가 LCA가 됩니다.
시간 복잡도: 초기화 \(O(n \log n)\), 질의당 \(O(\log n)\).
\(\texttt{코드:}\)
void initialize(int root) {
queue<int> q;
q.push(root);
depth[root] = 1;
while(!q.empty()) {
int cur = q.front();
q.pop();
for(int edge = head[cur]; edge != -1; edge = nxt[edge]) {
int child = dest[edge];
if(depth[child]) continue;
depth[child] = depth[cur] + 1;
anc[child][0] = cur;
for(int lev = 1; lev <= MAX_LV; lev++)
anc[child][lev] = anc[anc[child][lev-1]][lev-1];
q.push(child);
}
}
}
int find_lca(int u, int v) {
if(depth[u] > depth[v]) swap(u, v);
for(int lev = MAX_LV; lev >= 0; lev--)
if(depth[anc[v][lev]] >= depth[u])
v = anc[v][lev];
if(u == v) return u;
for(int lev = MAX_LV; lev >= 0; lev--)
if(anc[u][lev] != anc[v][lev])
u = anc[u][lev], v = anc[v][lev];
return anc[u][0];
}
2. 타잔 알고리즘
오프라인 알고리즘으로 DFS 탐색 중 노드를 세 가지 상태로 분류:
- 완료됨(2): 방문 및 백트래킹 완료
- 진행 중(1): 현재 방문 중인 노드 또는 조상
- 미방문(0)
노드 \(u\)를 방문할 때:
- 인접 노드 재귀적 탐색
- 서브트리 처리 후 유니온-파인드로 \(u\)를 부모에 병합
- \(u\) 관련 질의 중 상대 노드 상태가 2이면 \(\text{find}(v)\)가 LCA
시간 복잡도: \(O(n + m)\)
\(\texttt{코드:}\)
vector<pair<int, int>> queries[N];
int parent[N], visited[N], result[N];
int find_set(int x) {
return parent[x] == x ? x : parent[x] = find_set(parent[x]);
}
void tarjan(int u) {
visited[u] = 1;
for(int edge = head[u]; edge != -1; edge = nxt[edge]) {
int child = dest[edge];
if(visited[child]) continue;
tarjan(child);
parent[child] = u;
}
for(auto &q : queries[u]) {
int adj = q.first, idx = q.second;
if(visited[adj] == 2)
result[idx] = find_set(adj);
}
visited[u] = 2;
}
\(\texttt{0x02}\) 적용 사례
1. LCA를 통한 트리 정보 계산
트리 경로 거리: \(\text{dist}(x,y) = \text{dist}[x] + \text{dist}[y] - 2 \times \text{dist}[\text{LCA}(x,y)]\)
경로 특성 확인: 트리 경로 상 특정 속성(노드 타입, 깊이 제곱합) 존재 여부 판별 시 LCA로 경로 분할 후 결합법칙 적용
2. 트리 차분
경로 가중치 업데이트: \(x \to y\) 경로에 가중치 \(c\) 추가 시:
diff[x] += c;
diff[y] += c;
diff[lca] -= c;
diff[anc[lca][0]] -= c;
서브트리 합계 계산으로 최종 값 도출
3. 트리 경로 교차 판정
경로 \(A\to B\)와 \(C\to D\) 교차 여부:
bool paths_intersect(int a, int b, int c, int d) {
int ab = find_lca(a,b), cd = find_lca(c,d);
int ac = find_lca(a,c), ad = find_lca(a,d);
int bc = find_lca(b,c), bd = find_lca(b,d);
return (find_lca(ac, d) == cd && find_lca(ac, b) == ab) ||
(find_lca(ad, c) == cd && find_lca(ad, b) == ab) ||
(find_lca(bc, d) == cd && find_lca(bc, a) == ab) ||
(find_lca(bd, c) == cd && find_lca(bd, a) == ab);
}
4. 최적 집합점 탐색
세 노드 \(x,y,z\)와의 거리 합 최소점: 세 LCA 중 깊이가 최대인 노드 \(P\) 선택 최소 거리 합: \(\sum \text{dist}[x,y,z] + \text{dist}[P] - 2 \times \text{dist}[\text{LCA}(x,y,z)]\)
5. 최대 생성 트리와 LCA 결합
무방향 그래프 최대 대역폭 경로:
- 최대 생성 트리 구성
- 트리 내 \(x\to y\) 경로의 최소 간선 가중치 계산
int path_min(int u, int v) {
int res = INT_MAX;
if(depth[u] > depth[v]) swap(u,v);
for(int lev=MAX_LV; lev>=0; lev--)
if(depth[anc[v][lev]] >= depth[u]) {
res = min(res, min_val[v][lev]);
v = anc[v][lev];
}
if(u == v) return res;
for(int lev=MAX_LV; lev>=0; lev--)
if(anc[u][lev] != anc[v][lev]) {
res = min(res, min(min_val[u][lev], min_val[v][lev]));
u = anc[u][lev], v = anc[v][lev];
}
return min(res, min(min_val[u][0], min_val[v][0]));
}