최소 공통 조상 (LCA)

최소 공통 조상 (Lowest Common Ancestor / LCA)

정점 a와 정점 b가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때 처음으로 만나게 되는 공통 정점
정점 a의 조상이면서 정점 b의 조상인 정점들 중 가장 깊은 정점

트리에서 두 노드의 최단거리는 무조건 LCA를 지남

LCA 구하기

1. 최상위 조상 정점을 시작으로 BFS를 수행하여 각 정점의 깊이와 부모 정점 저장
2. 두 정점의 depth를 맞추고, 하나씩 올려가며 LCA 찾기

depth 맞춰줄 때 2^k만큼씩 depth를 올리자 → log 시간 수행 보장
각 정점의 부모 뿐 아니라 2^k번째 조상까지 저장
parent[k][v] = parent[k-1][parent[k-1][v]]

구현

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int root = 1;
int n; // #node
const int LOG = 17;
// 최대 노드(N) 수 보다 큰 가장 작은 2^n 값을 선택
// c.f. 2^15 < N=50000 < 2^16
// c.f. 2^16 < N=100000 < 2^17

vector<vector<int>> adjList;
vector<int> depth;
vector<vector<int>> parent;

void bfs() {
	queue<int> q;
	vector<bool> visited(n+1, false);

	q.push(root);
	visited[root] = true;
	depth[root] = 0;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		for (int next : adjList[cur]) {
			if (!visited[next]) {
				depth[next] = depth[cur] + 1;
				parent[0][next] = cur;

				visited[next] = true;
				q.push(next);
			}
		}
	}
}
void find_ancestors() {
	for (int i = 1; i <= LOG; i++) {
		for (int j = 1; j <= n; j++) {
			parent[i][j] = parent[i - 1][parent[i - 1][j]];
		}
	}
}
int find_LCA(int a, int b) {
	if (depth[a] > depth[b]) {
		int tmp = a;
		a = b;
		b = tmp;
	}

	for (int k = LOG; k >= 0; k--) {
		if ((depth[b] - depth[a]) >= (1 << k))
			b = parent[k][b];
	}

	if (a == b) return a;

	for (int k = LOG; k >= 0; k--) {
		if (parent[k][a] != parent[k][b]) {
			a = parent[k][a];
			b = parent[k][b];
		}
	}

	return parent[0][a];
}

int main() {
    cin >> n;
    
    adjList.resize(n + 1);
    depth.resize(n + 1);
    parent.assign(LOG + 1, vector<int>(n + 1, 0));

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    bfs(); 
    find_ancestors(); 

    int a, b;
    cin >> a >> b;
    find_LCA(a, b);

    return 0;
}