11437 LCA

https://www.acmicpc.net/problem/11437

트리에서 두 노드의 LCA (Lowest Common Ancestor), 즉 가장 가까운 공통 조상을 찾는 문제이다. Naive한 방법으로 O(N)만에 구할 수 있다. 모든 노드를 루트에서 시작하여 BFS (Breadth First Search)로 탐색하여 모든 노드의 부모와 깊이를 구한다. 그리고 LCA를 구하고자 하는 두 노드 중 더 깊은 노드를 올려서 두 노드의 깊이를 똑같이 맞춰준다. 그리고 하나씩 동시에 올리면서 처음 두 노드가 같아졌을 때 그 노드가 LCA이다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int n,m,u,v,p[50001],c[50001],d[50001];
vector<int> a[50001];
 
void bfs()
{
    p[1]=d[1]=0,c[1]=true;
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int now=q.front(); q.pop();
        for(int next : a[now])
        {
            if(c[next]) continue;
            c[next]=true;
            p[next]=now;
            d[next]=d[now]+1;
            q.push(next);
        }
    }
}
 
int lca(int u,int v)
{
    if(d[u]<d[v]) swap(u,v);
    while(d[u]!=d[v]) u=p[u];
    while(u!=v) u=p[u],v=p[v];
    return u;
}
 
int main()
{
    scanf("%d",&n);
    while(--n)
    {
        scanf("%d %d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    bfs();
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d %d",&u,&v);
        printf("%d\n",lca(u,v));
    }
    return 0;
}