Centroid Decomposition (min edge on path)

import std.stdio;
import std.algorithm;
import std.typecons;
import std.math;

alias pair = Tuple!(int, "num", int, "cost");

pair[][] g;
int[] level, parent;
int[][] dp;
int n, m;

int dfs(int u, int size, ref int center, int prev = -1){
    int sum = 1;
    foreach(v; g[u])
        if (v.num != prev && level[v.num] == -1)
            sum += dfs(v.num, size, center, u);
    if (center == -1 && (2 * sum >= size || prev == -1)) center = u;
    return sum;
}

void calc(int u, int depth, int dist = int.max, int prev = -1){
    dp[depth][u] = dist;
    foreach(v; g[u])
        if (v.num != prev && level[v.num] == -1)
            calc(v.num, depth, min(dist, v.cost), u);
}

void build(int u, int size, int depth, int prev = -1){
    int center = -1;
    dfs(u, size, center);
    level[center] = depth;
    parent[center] = prev;
    calc(center, depth);
    foreach(v; g[center])
        if (level[v.num] == -1)
            build(v.num, size / 2, depth + 1, center);
}

int get_center(int u, int v){
    while (level[u] > level[v]) u = parent[u];
    while (level[v] > level[u]) v = parent[v];
    while (u != v) u = parent[u], v = parent[v];
    return u;
}

int ans(int u, int v){
    int ls = get_center(u, v);
    return min(dp[level[ls]][u], dp[level[ls]][v]);
}

void main(){
    readf("%s\n", &n);
    g = new pair[][n];
    dp = new int[][](2 + cast(int)log2(n), n);
    level = new int[n + 1];
    parent = new int[n];
    level[] -= 1;
    foreach(i; 1..n){
        int u, w;
        readf("%s %s\n", &u, &w);
        --u;
        g[u] ~= pair(i, w);
        g[i] ~= pair(u, w);
    }
    build(0, n, 0);
    readf("%s\n", &m);
    foreach(i; 0..m){
        int u, v;
        readf("%s %s\n", &u, &v);
        writeln(ans(u - 1, v - 1));
    }
}