1761 정점들의 거리

LCA 문제다.

a,b 의 LCA를 찾는 동안 누적된 거리를 출력하면 된다.

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
typedef pair<int, int> pii;
 
int d[50001], n, u, v, m, w;
pii p[50001];
vector<pii> adj[50001];
void bfs(int nod) {
    queue<int> q;
    d[nod] = 1;
    q.push(nod);
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (auto i : adj[x]) {
            if (d[i.first]) continue;
            q.push(i.first);
            d[i.first] = d[x] + 1;
            p[i.first].first = x;
            p[i.first].second = i.second;
        }
    }
}
 
int main() {
    scanf("%d", &n);
    n--;
    while (n--) {
        scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    int i;
    for (i = 0; !adj[i].size(); i++);
    bfs(i);
    scanf("%d", &m);
    int ans;
    while (m--) {
        ans = 0;
        scanf("%d%d", &u, &v);
        while (d[u] < d[v]) {
            ans += p[v].second; v = p[v].first;
        }
        while (d[v] < d[u]) {
            ans += p[u].second; u = p[u].first;
        }
        while (u != v) {
            ans += p[v].second + p[u].second; 
            v = p[v].first;
            u = p[u].first;
        }
        printf("%d\n", ans);
    }
 
    return 0;
}