11437번

11437번 - LCA

가장 가까운 공통 조상을 찾는 문제,

LCA를 찾는 방법은 

첫번째, 두 노드의 깊이가 같을 때까지 맞춘다

두번째, 두 노드가 같아질 때까지 함께 위로 올린다.

처음에는 bfs를 안 쓰고 union-find 를 사용했는데, 기존에 사용했던 것보다 좀 고쳐서 써야할 점이 많았고,

입력이 내 입맛대로 들어오지 않아서 시간초과가 발생했다.

한번 전부 입력받고, bfs를 통해서 각 노드들의 깊이를 다시 만들어줬다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int p[50001];
int h[50001];
bool check[50001];
vector<int> v;
vector<vector<int>> vec(50001);
int LCA(int a, int b)
{
    while (h[a] != h[b])
    {
        if (h[a] > h[b])
        {
            a = p[a];
        }
        else
        {
            b = p[b];
        }
    }
 
    while (a != b)
    {
        a = p[a];
        b = p[b];
    }
 
    return a;
}
void bfs()
{
    queue<int> q;
    check[1] = true;
    h[1] = 1;
    p[1] = 1;
    q.push(1);
    
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
 
        for (int i = 0; i < vec[now].size(); i++)
        {
            int next = vec[now][i];
 
            if (!check[next])
            {
                check[next] = true;
                h[next] = h[now] + 1;
                p[next] = now;
                q.push(next);
            }
        }
    }
}
int main()
{
    //freopen("input.txt", "r", stdin);
 
    int n, m;
    scanf("%d", &n);
 
    for (int i = 1; i < n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
 
    bfs();
 
    scanf("%d",&m);
    while (m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        v.push_back(LCA(a, b));
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        printf("%d\n", v[i]);
    }
 
    return 0;
}