Heavy_Light

#include <iostream>
#include <vector>

#define int long long

using namespace std;

struct edge {
    int u;
    int v;
    int w;
};

vector<vector<edge>> edges;
vector<edge> parent;
vector<int> s;
vector<vector<int>> pathes;
vector<vector<int>> chains;
vector<int> global_chain;
vector<int> tin, tout;
vector<vector<int>> up;
vector<int> myChain;
vector<int> chainOffset;
vector<vector<int>> answer;
int n, m;

const int l = 15;

int calc_size(int index){
    int _count = 1;
    for (int i = 0; i < edges[index].size(); i++)
        _count += calc_size(edges[index][i].v);
    s[index] = _count;
    return _count;
}

void build_path(int index, int chain){
    bool flag = (chain != -1);

    if (chain == -1) {
        chain = pathes.size();
        pathes.resize(chain+1); pathes[chain].resize(0);
        chains.resize(chain+1); chains[chain].resize(0);
    }
    pathes[chain].push_back(index);
    if (flag) chains[chain].push_back(parent[index].w);
    myChain[index] = chain;

    int _max = 0, child;
    for (int i = 0; i < edges[index].size(); i++){
        int to = edges[index][i].v;
        if (_max < s[to]) {
            _max = s[to];
            child = to;
        }
    }

    if (_max > 0) build_path(child, chain);

    for (int i = 0; i < edges[index].size(); i++){
        int to = edges[index][i].v;
        if (to != child) build_path(to, -1);
    }
}

void reverse_chains(int num){
    if (num == chains.size()) return;
    int _size = chains[num].size();
    for (int i = 0; i < _size/2; i++)
        swap(chains[num][i], chains[num][_size-1-i]);
    reverse_chains(num+1);
}

void build_global_chain(){
    int _size = 0;
    for (int i = 0; i < chains.size(); i++)
        _size += chains[i].size();

    for (m = 1; m < _size; m *= 2);

    global_chain.resize(2*m, 0);
    chainOffset.resize(chains.size());

    int offset = 0;
    for (int i = 0; i < chains.size(); i++){
        for (int j = 0; j < chains[i].size(); j++)
            global_chain[offset + j + m] = chains[i][j];
        chainOffset[i] = offset;
        offset += chains[i].size();
    }

    for (int i = m-1; i > 0; i--)
        global_chain[i] = global_chain[i*2] + global_chain[i*2+1];
}

int timer;
void dfs(int index, int parent){
    if (index == 0) timer = 0;
    tin[index] = ++timer;
    up[index][0] = parent;
    for (int i = 1; i < l; i++)
        up[index][i] = up[up[index][i-1]][i-1];

    for (int i = 0; i < edges[index].size(); i++)
        dfs(edges[index][i].v, index);

    tout[index] = ++timer;
}

bool upper(int a, int b){
    return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}

int lca(int a, int b){
    if (upper(a,b)) return a;
    if (upper(b,a)) return b;

    for (int i = l-1; i >= 0; i--){
        while (!upper(up[a][i], b)) a = up[a][i];
    }

    return up[a][0];
}

int _find(int index, int chain){
    int l = 0; int r = pathes[chain].size()-1;
    int m;
    while (r-l > 1){
        m = (l+r)/2;
        if (pathes[chain][m] < index) l = m; else r = m;
    }

    if (pathes[chain][l] == index) return l;
    if (pathes[chain][r] == index) return r;
    return -1;
}

int calcDistToLCA(int index, int _lca){
    int chain = myChain[index];
    int r = _find(index, chain);
    int l = _find(_lca, chain);
    bool flag = (l == -1);
    if (l == -1) l = 0;

    l = m + chainOffset[chain] + l;
    r = m + chainOffset[chain] + r - 1;

    int sum = 0;

    if (r >= l){
        while (l != r){
            if (r > l){
                if (r % 2 == 1) r /= 2; else {
                    sum += global_chain[r];
                    r--;
                }
            } else {
                if (l % 2 == 0) l /= 2; else {
                    sum += global_chain[l];
                    l++;
                }
            }
        }
        sum += global_chain[l];
    }

    if (flag){
        edge _parent = parent[pathes[chain][0]];
        sum += calcDistToLCA(_parent.u, _lca) + _parent.w;
    }

    return sum;
}

int getDistOnWay(int a, int b){
    int _lca = lca(a, b);

    return calcDistToLCA(a, _lca) + calcDistToLCA(b, _lca);
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    if (n == 0) {
        for (int i = 0; i < answer.size(); i++){
            for (int j = 0; j < answer[i].size(); j++) cout << answer[i][j] << " ";
            cout << endl;
        }
        return 0;
    }
    answer.resize(answer.size()+1);

    edges.resize(n); for (int i = 0; i < n; i++) edges[i].resize(0);
    s.resize(n);
    parent.resize(n);
    tin.resize(n);
    tout.resize(n);
    up.resize(n); for (int i = 0; i < n; i++) up[i].resize(l);
    pathes.resize(0);
    chains.resize(0);
    global_chain.resize(0);
    myChain.resize(n);

    edge e;
    for (int i = 1; i < n; i++){
        cin >> e.u >> e.w;
        e.v = i;
        edges[e.u].push_back(e);
        parent[i] = e;
    }

    calc_size(0);
    build_path(0, -1);
    build_global_chain();
    dfs(0, 0);

    int q; cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        answer[answer.size()-1].push_back(getDistOnWay(a, b));
    }

    main();

    return 0;
}