URI PROBLEMA 1135 - Colônia de Formigas SOLUÇÃO EM C++

URI Online Judge | 1135

Colônia de Formigas

por Pablo Ariel Heiber  Argentina

Timelimit: 2

Um grupo de formigas está muito orgulhoso pois construíram uma grande e magnífica colônia. No entanto, seu enorme tamanho tem se tornado um problema, pois muitas formigas não sabem o caminho entre algumas partes da colônia. Elas precisam de sua ajuda desesperadamente!

 

A colônia de formigas foi criada como uma série de N formigueiros conectados por túneis. As formigas, obssessivas como são, numeraram os formigueiros sequencialmente à medida que os construiam. O primeiro formigueiro, numerado 0, não necessitava nenhum túnel, mas para cada um dos formigueiros subsequentes, 1 até N-1, as formigas também construíram um único túnel que conectava o novo formigueiro a um dos formigueiros existentes. Certamente, esse túnel era suficiente para permitir que qualquer formiga visitasse qualquer formigueiro já construído, possivelmente passando através de outros formigueiros pelo percurso, portanto elas não se preocupavam em fazer novos túneis e continuavam construindo mais formigueiros.

 

O seu trabalho é: dada a estrutura de uma colônia e um conjunto de consultas, calcular, para cada uma das consultas, o menor caminho entre pares de formigueiros. O comprimento do caminho é a soma dos comprimentos de todos os túneis que necessitam ser visitados.

Entrada

Cada caso de teste se estende por várias linhas. A primeira linha contém um inteiro N representando a quantidade de formigueiros na colônia (2 ≤ N ≤ 105). 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 formigueiro i foi conectado diretamente ao formigueiro Ai por um túnel de comprimento Li (0 ≤ Ai ≤ i-1 e 1 ≤ Li ≤ 109). A próxima linha contém um inteiro Qrepresentando o número de consultas que seguem (1 ≤ Q ≤ 105). 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, os formigueiros de origem e destino.

 

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 formigueiros de cada consulta. Escreva os resultados para cada consulta na mesma ordem em que aparecem na entrada.

#include <cstdio>

#include <vector>

#include <algorithm>

#define gc getchar_unlocked

void getint(int &x){

    register int c = gc();

    x = 0;

    for(;(c<48 || c>57);c = gc());

    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}

}

using namespace std;

#define MAXN 100001

#define LIMIT 1000000001

int n,q,nivel[MAXN],pai[MAXN];

long long int raiz[MAXN];

int LCA(int u, int v){

while(u!=v){

if (nivel[u]>nivel[v]) u = pai[u];

else v = pai[v];

}

return u;

}

int main(){

while(1){

getint(n);

if (n == 0) break;

raiz[0]=0LL;

nivel[0]=0;

pai[0]=0;

for(int i=1;i<n;i++){

int a,b;

getint(a);

getint(b);

pai[i]=a;

nivel[i]= nivel[a]+1;

raiz[i]= raiz[a]+b;

}

getint(q);

bool verdade = false;

while(q--){

if (verdade) printf(" ");

int x,y;

getint(x);

getint(y);

printf("%lld",raiz[x]+raiz[y]-2*raiz[LCA(x,y)]);

verdade=true;

}

printf("\n");

}

return 0;

}