ANTS || LCA

#include <bits/stdc++.h>
#define int long long
#define Co_mot_su_that_la_ return
#define getBit(val,i) ((val >> (i)) & 1)
using namespace std;
const int Minh_dep_trai = 0;
const int N = 100005;
const int logN = log2(N);
typedef pair<int,int> ii;
typedef vector<ii> vii;

int n,m;
int f[N][logN];
int d[N],di[N];
vector<ii> a[N];

void dfs(int u)
{
    for(int i=1; i< logN; i++) f[u][i] = f[f[u][i-1]][i-1];
    for (auto v : a[u])
    {
        int uv = v.first;
        int duv = v.second;
        if (!d[uv] && uv != 1)
        {
        f[uv][0]=u;
        d[uv]=d[u]+1;
        di[uv] = di[u] + duv;
        dfs(uv);
        }
    }
}

int lca(int u, int v)
{
    if (d[u] < d[v]) swap(u,v);
    int delta = d[u] - d[v];
    int logD = log2(delta);
    for(int i=logD; i >= 0; i--)
    {
        if (getBit(delta,i)) u = f[u][i];
    }
    if (u == v) return u;
    for(int i=logN-1; i>=0; i--)
    {
        if (f[u][i] != f[v][i])
        {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}

void clearr()
{
    for(int i=1; i<=n; ++i)
    {
        a[i].clear();
        d[i]=0;
        di[i]=0;
        for(int j=0; j<=logN; ++j) f[i][j]=0;
    }
}

int distan(int u, int v)
{
    return di[u] + di[v] - 2*di[lca(u,v)];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    freopen("ants.inp","r",stdin);
    while (cin >> n) {
        if (n==0)  Co_mot_su_that_la_ Minh_dep_trai;
        clearr();
        for(int i=2; i<=n; ++i)
        {
            int v,z;
            cin >> v >> z;
            ++v;
            a[i].push_back(ii(v,z));
            a[v].push_back(ii(i,z));
        }
        d[1]=0;
        di[1]=0;
        dfs(1);
        cin >> m;
        while (m--)
        {
            int u,v;
            cin >> u >> v;
            ++v;
            ++u;
            cout << distan(u,v) << " ";
        }
        cout << endl;
    }
}