1761번: 정점들의 거리

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

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 40000, LGN = 15;
int n, m;
int dp[MAX_N + 1][LGN + 1], lv[MAX_N + 1], dist[MAX_N + 1];
bool ck[MAX_N + 1];
vector<pair<int, int> > adj[MAX_N + 1];
void dfs(int h) {
    ck[h] = true;
    for (auto it : adj[h]) {
        if (ck[it.first]) continue;
        dist[it.first] = dist[h] + it.second;
        lv[it.first] = lv[h] + 1;
        dp[it.first][0] = h;
        for (int i = 1; i <= LGN; i++)
            dp[it.first][i] = dp[dp[it.first][i - 1]][i - 1];
        dfs(it.first);
    }
}
int lca(int x, int y) {
    if (lv[x] < lv[y]) swap(x, y);
    for (int i = LGN; i >= 0; i--)
        if (1 << i <= lv[x] - lv[y]) x = dp[x][i];
    if (x == y) return x;
    for (int i = LGN; i >= 0; i--)
        if (dp[x][i] != dp[y][i])
            x = dp[x][i], y = dp[y][i];
    return dp[x][0];
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({ b, c });
        adj[b].push_back({ a, c });
    }
    dfs(1);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", dist[a] + dist[b] - 2 * dist[lca(a, b)]);
    }
    return 0;
}