BOJ 1761 정점들의 거리

void dfs(int cur, int _par){
    for(auto [nxt, w]: links[cur]){
        if(nxt == _par) continue;
        dist[nxt] = dist[cur] + w;
        depth[nxt] = depth[cur] + 1;
        par[nxt][0] = cur;
        dfs(nxt, cur);
    }
}

int LCA(int u, int v){
    if(u == v) return u;
    if(depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    rep(i, 0, 16) if((diff >> i) & 1) u = par[u][i];
    if(u == v) return u;
    rrep(i, 16, 0){
        if(par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}

ll getDist(int u, int v){
    int lca = LCA(u, v);
    return dist[u] + dist[v] - 2 * dist[lca];
}

void solve(){
    cin >> N;
    rep(i, 0, N-1){
        int u, v, w; cin >> u >> v >> w;
        links[u].push_back({v, w});
        links[v].push_back({u, w});
    }

    dfs(1, -1);
    rep(j, 1, 16) rep(i, 1, N+1) par[i][j] = par[par[i][j-1]][j-1];
    cin >> Q;
    while(Q--){
        int u, v; cin >> u >> v;
        cout << getDist(u, v) << '\n';
    }
}