지나치는 노드들 (JUNGOL 8397)

https://jungol.co.kr/problem/8397?cursor=MTIsMiw0

---

아이디어

간선의 가중치가 2^x의 꼴이므로 경로의 가중치의 합이 최소가 되기 위해서는 경로상에 존재하는 최대의 x값을 최소화해야합니다. 이는 x값이 증가하는 순서대로 관찰하며 스패닝 트리를 만들었을 때 그 트리상의 경로와 같아지게 됩니다. 그러므로 x가 증가하는 순서대로 스패닝 트리를 만들고, 그 스패닝 트리에서 LCA를 통하여 경로상의 정점의 개수를 세어주면 됩니다.

---

소스코드

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

ll par[202020]={0};
ll find(ll x)
{
    if (x==par[x]) return x;
    return par[x]=find(par[x]);
}
void Union(ll x,ll y)
{
    par[find(x)]=find(y);
}
bool same(ll x,ll y)
{
    return find(x)==find(y);
}

ll ParNode[202020][22]={0},dpt[202020]={0};
vector <ll> Graph[202020];

void DFS(ll node,ll before)
{
    ParNode[node][0]=before;
    dpt[node]=dpt[before]+1;
    for (ll i=1;i<=20;i++)
        ParNode[node][i]=ParNode[ParNode[node][i-1]][i-1];

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

ll solve(ll a,ll b)
{
    if (dpt[a]<dpt[b]) swap(a,b);
    ll res=0;
    
    for (ll i=20;i>=0;i--)
    {
        if (dpt[ParNode[a][i]]>=dpt[b])
        {
            a=ParNode[a][i];
            res+=1<<i;
        }
    }

    if (a==b) return res-1;

    for (ll i=20;i>=0;i--)
    {
        if (ParNode[a][i]!=ParNode[b][i])
        {
            a=ParNode[a][i];
            b=ParNode[b][i];
            res+=1<<(i+1);
        }
    }

    return res+1;
}

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

    cin>>N>>M;
    for (i=1;i<=N;i++) par[i]=i;

    for (i=0;i<M;i++)
    {
        cin>>a>>b;
        if (same(a,b)) continue;
        Union(a,b);
        Graph[a].push_back(b);
        Graph[b].push_back(a);
    }

    DFS(1,0);

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