Solução por Lucca Siaudzionis
Este problema é um problema básico se for resolvido pelo algoritmo do Mínimo Ancestral Comum (LCA - Lowest Common Ancestor). Há duas maneiras típicas de fazer, uma em 
e outra em 
. Você pode aprender a fazer o o LCA em 
na nossa aula do Curso Noic de Informática, clicando aqui. Além disso, um material que explica (em português!) muito bem o LCA em 
pode ser visto neste link.
Seguindo o mesmo estilo que se faz no material, o código fica assim:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |