TUMSO-16: Ant Colony

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
using pll = pair <lli, lli>;
const lli maxN = 1e5;
const lli logN = log2(maxN);
vector <pll> g[maxN + 10];
lli level[maxN + 10], par[maxN + 10][logN + 10], dis[maxN + 10][logN + 10];
lli n;

void dfs(lli u, lli p, lli lvl, lli pw){
    level[u] = lvl;
    par[u][0] = p;
    dis[u][0] = pw;
    for(auto vw: g[u]){
        lli v = vw.first;
        lli w = vw.second;
        if(v != p){
            dfs(v, u, lvl + 1, w);
        }
    }
}

lli LCA_Dis(lli u, lli v){ /// u -> v
    if(level[u] < level[v]) swap(u, v);
    lli sum = 0;
    for(lli e=logN;e>=0;e--){
        if(level[ par[u][e] ] >= level[v]){
            sum += dis[u][e];
            u = par[u][e];
        }
    }
    if(u == v) return sum;
    for(lli e=logN;e>=0;e--){
        if(par[u][e] != par[v][e]){
            sum += dis[u][e];
            u = par[u][e];
            sum += dis[v][e];
            v = par[v][e];
        }
    }
    sum += dis[u][0];
    sum += dis[v][0];
    return sum;
}

int main(){

    scanf("%lld", &n);

    for(lli u=1;u<=n-1;u++){
        lli v, w;
        scanf("%lld %lld", &v, &w);
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    dfs(0, 0, 1, 0);

    for(lli e=1;e<=logN;e++){
        for(lli u=0;u<=n;u++){
            par[u][e] = par[ par[u][e - 1] ][e - 1];
            dis[u][e] = dis[u][e - 1] + dis[ par[u][e - 1] ][e - 1];
        }
    }

    lli q;
    scanf("%lld", &q);

    while(q--){
        lli u, v;
        scanf("%lld %lld", &u, &v);
        printf("%lld\n", LCA_Dis(u, v));
    }

    return 0;
}