트리의 공통 조상 (JUNGOL 3599)

https://jungol.co.kr/problem/3599?cursor=MTIsMiwz

---

아이디어

LCA를 구현하여주면 됩니다.

---

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

vector <ll> Graph[303030];
ll dpt[303030]={0},par[303030][22]={0};
void DFS(ll node,ll before)
{
    dpt[node]=dpt[before]+1;
    par[node][0]=before;
    for (ll i=1;i<=20;i++) par[node][i]=par[par[node][i-1]][i-1];

    for (ll next:Graph[node])
        if (next!=before)
            DFS(next,node);
}

ll LCA(ll a,ll b)
{
    if (dpt[a]<dpt[b]) swap(a,b);
    for (ll i=20;i>=0;i--)
    {
        if (dpt[par[a][i]]>=dpt[b])
            a=par[a][i];
    }
    if (a==b) return a;
    for (ll i=20;i>=0;i--)
    {
        if (par[a][i]!=par[b][i])
            a=par[a][i],b=par[b][i];
    }
    return par[a][0];
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,a,b,Q;

    cin>>N;
    for (i=0;i<N-1;i++)
    {
        cin>>a>>b;
        Graph[a].push_back(b);
        Graph[b].push_back(a);
    }
    DFS(1,0);

    cin>>Q;
    for (i=1;i<=Q;i++)
    {
        cin>>a>>b;
        cout<<LCA(a,b)<<"\n";
    }
}