1761 정점들의 거리

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

트리에서의 두 정점 사이의 경로는 하나만 존재하므로 경로 사이의 거리가 곧 최단 거리가 된다. 이 점을 이용하여 루트에서 부터의 정점 i까지의 거리를 d[i]라 하면 두 정점 u,v 사이의 거리는 d[u]+d[v]에서 경로에 해당되지 않는 부분인 d[lca(u,v)]가 두 번 포함되었으므로 dist(u,v)=d[u]+d[v]-2*d[lca(u,v)] 이다.

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