==Include(page="template/taskheader" task_id="delay")==
== include(page="template/taskheader" task_id="delay") ==
==include(page="template/badtests")==
Gigel a cumparat $N$ calculatoare cu care vrea sa deschida un Internet Cafe. Pentru aceasta, el trebuie sa conecteze toate calculatoarele in retea, in asa fel incat oricare doua calculatoare sa poata comunica intre ele, direct sau indirect. Comunicatia dintre calculatoare se realizeaza prin intermediul cablurilor de legatura. Un cablu leaga doua calculatoare, iar transferul de date prin cablu se poate realiza in ambele sensuri. Fiind la inceput si neavand prea multi bani, Gigel a legat calculatoarele intre ele astfel incat intre oricare doua calculatoare exista un singur traseu pe care se pot transmite date.
Curand si-a dat seama ca transferul de date se realizeaza cu viteza foarte mica. Acest lucru se datoreaza faptului ca fiecare pachet de date care trece prin calculatorul $i$ este pus sa astepte un timp {$T{~i~}$}. In aceste conditii, timpul dupa care un pachet de date ajunge de la un calculator la altul este egal cu suma timpilor de asteptare ai fiecarui calculator de pe traseu (inclusiv ai calculatoarelor sursa si destinatie).
Din cand in cand, configuratia anumitor calculatoare este modificata si timpii de asteptare corespunzatori acelor calculatoare se schimba. Cum Gigel are grija foarte mare de calculatoarele sale, el trebuie sa fie mereu informat in legatura cu starea retelei. Mai precis, el trebuie sa poata afla repede care este timpul de transmitere a unui pachet de date intre oricare doua calculatoare din reteaua sa.
Poveste ...
h2. Cerinta
Scrieti un program care trateaza in mod eficient urmatoarele doua tipuri de operatii:
* tipul 1: modificarea timpului de asteptare al unui calculator
* tipul 2: determinarea timpului de transmitere a unui pachet de date intre doua calculatoare specificate.
h2. Date de Intrare
...
Pe prima linie a fisierului de intrare $delay.in$ se afla numarul $N$ de calculatoare. Pe fiecare dintre urmatoarele $N$ linii se afla cate un numar intreg {$T{~i~}$}, reprezentand timpul initial de asteptare al calculatorului corespunzator. Pe urmatoarele $N-1$ linii se afla cate doua numere intregi $a$ si {$b$}, reprezentand numerele a doua calculatoare legate printr-un cablu direct. Pe urmatoarea linie se afla numarul intreg {$M$}, reprezentand numarul de operatii descrise in continuare. Fiecare dintre urmatoarele $M$ linii contine cate $3$ numere intregi separate prin spatii: {$a b c$}.
h2. Restrictii
* Daca {$a=1$}, atunci $b$ reprezinta numarul de ordine al unui calculator nou configurat, iar $c$ reprezinta noul timp de asteptare al calculatorului $b$
* Daca {$a=2$}, atunci $b$ si $c$ reprezinta numerele de ordine a doua calculatoare diferite, iar programul va trebui sa afiseze in fisierul de iesire timpul de transmitere a unui pachet de date intre calculatoarele $b$ si $c$
...
h2. Date de Iesire
h2. Date de intrare
In fisierul $delay.out$ veti afisa, pe cate o linie separata, timpii determinati in cazul fiecarei operatii de tipul {$2$}, in ordinea in care sunt intalnite in fisierul de intrare. Atunci cand calculati timpul de transmitere a unui pachet de date intre doua calculatoare, trebuie sa considerati timpii de asteptare de la momentul respectiv (care sunt determinati de valorile initiale sau de operatiile de tipul $1$ descrise in fisierul de intrare inaintea operatiei curente).
...
h2. Restrictii si precizari
h2. Date de iesire
* $2 ≤ N ≤ 16.000$
* $0 ≤ T{~i~} ≤ 1.000$
* $2 ≤ M ≤ 200.000$
* Calculatoarele sunt numerotate de la $1$ la $N$
* In fisierul de intrare va exista cel putin o operatie de tipul $2$
...
h2. Exemplu
table(example). |_. delay.in |_. delay.out |
| 5
1
2
3
4
5
1 2
1 3
2 4
3 5
6
2 1 4
2 3 1
1 1 100
2 1 4
2 2 4
2 2 3
| 7
4
106
6
105 |
==Include(page="template/taskfooter" task_id="delay")==
| delay.in | delay.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="delay") ==
