BOJ 1761 - 정점들의 거리

문제 태그:https://www.acmicpc.net/problem/1761

문제 소개 

간선의 길이가 있는 트리가 주어지고, 두 정점이 계속해서 주어지면, 그 두 정점사이의 거리를 계속 답하면 된다.

문제 풀이

 LCA의 성질을 이용하면 쉽게 이 문제를 해결할 수 있다 a와 b의 LCA를 c라고 했을 때, a와 b사이의 거리는 a와 c사이의 거리+b와 c사이의 거리이다. 하지만 이것도 두 정점사이의 거리이므로, 좀 더 쉽게 이 문제를 해결하기 위해서 관점을 바꾸어보면, a와 b사이의 거리는 루트에서 a까지의 거리+루트에서 b까지의 거리- 2*루트에서 c까지의 거리이다.
 우리는 dfs를 돌리는 과정에서 루트에서 어떤 정점까지의 거리를 쉽게 구할 수 있다. 또한 LCA는 이글에 따르면 전처리 과정 $O(NlgN)$으로 한 번에 로그의 시간 복잡도로 구할 수 있다. 따라서 이 문제를 총 시간복잡도 $O((N+M)lgN)$에 해결할 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll>pii;
#define ff first
#define ss second
 
ll n,m;
ll par[50505][21];
ll vis[50505];
ll vis2[50505];
vector<pii> v[50505];
ll dep[50505];
ll dep2[50505];
 
void dfs(ll x,ll d){
    vis[x]=1;
    dep[x]=d;
    for(auto n:v[x]){
        if(vis[n.ss]) continue;
        par[n.ss][0]=x;
        dep2[n.ss]=dep2[x]+n.ff;
        dfs(n.ss,d+1);
    }
}
 
void f(){
    ll i,j;
    for(j=1;j<21;j++)
        for(i=1;i<=n;i++)
            par[i][j]=par[par[i][j-1]][j-1];
}
 
ll lca(ll x,ll y){
    if(dep[x]>dep[y]) swap(x,y);
    for(int i=20 ;i>=0;i--){
        if(dep[y]-dep[x]>=(1<<i)) y=par[y][i];
    }
 
    if(x==y) return x;
    for(int i=20;i>=0;i--){
        if(par[x][i]!=par[y][i]){
            x=par[x][i];
            y=par[y][i];
        }
    }
    return par[x][0];
}
 
int main(){
    scanf("%lld",&n);
    ll i,j,k,l,m,a,b,c;
    for(i=1;i<n;i++){
        scanf("%lld %lld %lld",&a,&b,&c);
        v[a].emplace_back(c,b);
        v[b].emplace_back(c,a);
    }
 
    dfs(1,0);
    f();
 
    scanf("%lld",&m);
    for(i=1;i<=m;i++){
        scanf("%lld %lld",&a,&b);
        printf("%lld\n",dep2[a]+dep2[b]-2*dep2[lca(a,b)]);
    }
}