tuneis.cpp

#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;
 
//----------------------
#define MAXN 100100
typedef long long lint;
 
int n;
lint dist[MAXN]; //distancia pro 0
bool visited[MAXN];
vector<int> grafo[MAXN];
 
int segmento;
int pai[MAXN];
int nivel[MAXN];
int super_pai[MAXN];
//----------------------
 
void monta_super_pai(int x, int p){
     
    visited[x] = 1;
    super_pai[x] = p;
     
    if(nivel[x] % segmento == x) p = x;
     
    for(int i = 0;i < grafo[x].size();i++)
        if(!visited[grafo[x][i]])
            monta_super_pai(grafo[x][i], p);
}
 
int lca(int a, int b){
     
    while(super_pai[a] != super_pai[b]){
        if(nivel[a] > nivel[b]) a = super_pai[a];
        else b = super_pai[b];
    }
     
    while(a != b){
        if(nivel[a] > nivel[b]) a = pai[a];
        else b = pai[b];
    }
     
    return a;
}
 
int main(){
     
    while(scanf("%d", &n) && n){
         
        segmento = 0;
        for(int i = 0;i < n;i++) grafo[i].clear(), visited[i] = false, dist[i] = 0LL, super_pai[i] = -1, nivel[i] = 0;
         
        for(int i = 1;i < n;i++){
            int x;
            lint d;
            scanf("%d %lld", &x, &d);
             
            grafo[x].push_back(i);
             
            pai[i] = x;
            dist[i] = dist[x] + d;
            nivel[i] = nivel[x] + 1;
             
            if(nivel[i] > segmento) segmento = nivel[i];
        }
         
        //printf("%d %d\n", nivel[0], nivel[1]);
        //printf("%d\n", segmento);
        segmento = (int)floor(sqrt(segmento));
        monta_super_pai(0, 1);
         
        int q;
        scanf("%d", &q);
        for(int i = 1;i <= q;i++){
            int a, b;
            scanf("%d %d", &a, &b);
             
            if(i > 1) printf(" ");
            printf("%lld", dist[a] + dist[b] - 2*dist[lca(a, b)]);
        }
        printf("\n");
    }
     
    return 0;
}