BOJ 1761

#include <iostream>
#include <vector>
#include <cmath>
#define MAXN 40000+1
#define swap(a,b){int t = a; a= b; b = t;}

using namespace std;

vector<pair<int,int> > adj[MAXN];
int depth[MAXN];
int dist[MAXN];
int par[MAXN][20];
bool visited[MAXN];
int max_level = 20;
int N,M;

void getTree(int idx, int d, int cnt){
    visited[idx] = true;
    depth[idx] = d;
    dist[idx] = cnt;
    for (int i = 0 ; i <adj[idx].size(); i++){
        int there = adj[idx][i].first;
        if (visited[there]) continue;
        getTree(there,d+1,cnt+adj[idx][i].second);
        par[there][0] = idx;
    }
}
int LCA(int a, int b){
    // a와 b의 depth 같게 만들기
    if (depth[a] != depth[b]){
        if (depth[a] > depth[b]) swap(a,b);
        for (int i = max_level-1; i >=0; i--){
            if (depth[a] <= depth[par[b][i]]){
                b = par[b][i];
            }
        }
    }
    int lca = a;
    if (a!=b){
        for (int i = max_level-1; i>=0; i--){
            if (par[a][i]!= par[b][i]){
                a = par[a][i];
                b = par[b][i];
            }
            lca = par[a][i];
        }
    }
    return lca;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i = 0 ;i <N-1;i++){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    // 트리 만들기
    getTree(1,0,0);
    for (int i = 1; i < max_level; i++){
        for (int j = 1; j <= N; j++){
            par[j][i] = par[par[j][i-1]][i-1];
        }
    }
    cin >> M;
    while (M--){
        int a,b;
        cin >> a >> b;
        cout << dist[a] + dist[b] - 2*dist[LCA(a,b)]<<"\n";
    }
    return 0;
}