Avançado Informática - Semana 4

Túneis Subterrâneos

 

Daniboy é um jovem tenista muito promissor. Aos 16 anos, já disputa os maiores campeonatos de tênis da atualidade. Todos sabemos que o maior e mais tradicional torneio de tênis é o Vietnã Open de Tênis, disputado pelas maiores lendas do esporte. Daniboy viajou ao Vietnã para tentar ser o mais novo tenista a ganhar o torneio na história e, como um bom turista, quis ir conhecer os famosos túneis que os vietcongues cavaram durante a Guerra do Vietnã para se locomover sem serem notados e fazerem ataques surpresas às forças americanas.

Os túneis ligam N pequenos quartéis subterrâneos. Cada quartel tem um número de identificação que vai de 0 a N-1. Uma curiosidade interessante é que os túneis foram cavados de modo que entre quaisquer dois quartéis existe exatamente um caminho subterrâneo que os liga. Durante a visita, Daniboy acabou se perdendo do grupo e agora precisa saber a distância entre o quartel que ele está e o quartel de saída.  Felizmente, ele encontrou um pequeno mapa que apresenta todos os túneis, dizendo os números dos quartéis que eles ligam e seus comprimentos. Como Daniboy não lembra ao certo em qual quartel ele está e onde fica a saída, ele lhe fará uma série de perguntas, apresentando dois quartéis (possível saída e possível atual) e lhe pedirá a distância entre eles.

Entrada

Cada caso de teste se estende por várias linhas. A primeira linha contém um inteiro N representando a quantidade de quartéis nos túneis subterrâneos (2 ≤ N ≤ 10^5). Cada uma das próximas N-1 linhas contém dois inteiros que descrevem um túnel. A linha i, para 1 ≤ i ≤ N-1, contém Ai e Li, indicando que o quartel foi conectado diretamente ao quartel Ai por um túnel de comprimento Li (0 ≤ Ai ≤ i-1 e 1 ≤ Li ≤ 10^9). A próxima linha contém um inteiro Q representando o número de consultas que seguem (1 ≤ Q ≤ 10^5). Cada uma das Q linhas seguintes descreve uma consulta e contém dois inteiros distintos S e T(0 ≤ S,T ≤ N-1), representando, respectivamente, o possível quartel em que Daniboy está e a possível saída dos túneis.

O último caso de teste é seguido por uma linha contendo apenas um zero.

Saída

Para cada caso de teste, imprima uma única linha com Q inteiros, os comprimentos do menor caminho entre os dois quartéis de cada consulta. Escreva os resultados para cada consulta na mesma ordem em que aparecem na entrada.

Exemplo de Entrada Exemplo de Saída
6
0 8
1 7
1 9
0 3
4 2
4
2 3
5 2
1 4
0 3
2
0 1
2
1 0
0 1
6
0 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
1
5 0
0
16 20 11 17
1 1
5000000000