(least common ancestor, LCA)

두 노드를 모두 자손으로 갖는 노드 중 가장 아래 있는 노드 구하기

예를 들어, LCA(2, 5) = 1, LCA(8, 5) = 0, LCA(1, 4) = 1

느린 버전 (그냥 1씩 올라가는 거)

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

int N, M;
int u, v;
queue<int> q;
vector<int> node[50001];
// 양방향이라 check 해줘야 함
bool check[50001];
int parent[50001];
int depth[50001];

int LCA(int u, int v)
{
	// v가 u보다 더 깊은 노드로 세팅
	if (depth[u] > depth[v]) swap(u, v);

	// 두 노드의 깊이가 같아질때까지 v노드는 위로 거슬러 올라감
	while (depth[u] != depth[v]) v = parent[v];

	// 두 노드가 같아질때 까지 위로 거슬러 올라감
	while (u != v)
	{
		u = parent[u];
		v = parent[v];
	}
	return u; // LCA 리턴
}

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0);

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

	check[1] = true;
	q.push(1); // 트리의 루트 

	while (!q.empty())
	{
		int x = q.front(); // 부모 노드
		q.pop();

		for (int i = 0; i < node[x].size(); i++)
		{
			if (!check[node[x][i]]) // 현재노드를 방문한적 없다면
			{
				depth[node[x][i]] = depth[x] + 1; // 깊이 +1
				check[node[x][i]] = true; // 방문표시
				parent[node[x][i]] = x; // 부모노드 입력
				q.push(node[x][i]); // 큐에 추가
			}
		}
	}

	cin >> M;

	for (int i = 0; i < M; i++)
	{
		cin >> u >> v;
		cout << LCA(u, v) << '\\n';
	}

	return 0;
}

빠른 버전 (2^n씩 올라가는 거)

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

int n, m;

vector<int> v[50001];
bool visited[50001];
int deep[50001]; //노드의 깊이.
int parent[50001][16];
int max_level; //최대깊이.

void dfs(int cur, int depth)
{
    deep[cur] = depth;
    for (int i = 0; i < v[cur].size(); i++)
    {
        int child = v[cur][i];
        if (!visited[child])
        {
            visited[child] = true;
            parent[child][0] = cur; // 2^0번째 조상 
            dfs(child, depth + 1);
        }
    }
}
void dp()
{
    //현재노드의 2^p번째 조상은 2^p-1 번째 조상의 2^p-1 번째 조상.
    for (int p = 1; p <= max_level; p++)
    {
        for (int cur = 1; cur <= n; cur++)
        {
            parent[cur][p] = parent[parent[cur][p - 1]][p - 1];
        }
    }
}
int lca(int x, int y) {
    if (deep[x] > deep[y])
        swap(x, y);
    for (int i = max_level; i >= 0; i--) {
        if (deep[y] - deep[x] >= (1 << i))
            y = parent[y][i];
    }
    if (x == y)return x;
    for (int i = max_level; i >= 0; i--) {
        if (parent[x][i] != parent[y][i]) {
            x = parent[x][i];
            y = parent[y][i];
        }
    }
    return parent[x][0];
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n; //정점의 개수.
    for (int i = 1; i <= n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    max_level = (int)floor(log2(n)); //최대 2^i번째가 가능한 레벨.
    visited[1] = true;
    dfs(1, 0);
    dp();
    cin >> m;
    while (m-- > 0)
    {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << "\\n";
    }
    return 0;
}

백준 문제

썩은 사과 나무가지 자르는데 최소한의 사과 떨어지게