== include(page="template/taskheader" task_id="taristraine") ==

Poveste şi cerinţă...

Cum protagonistul nostru, Sorin Pastrama, este seful la bani, acesta isi doreste sa plece in tari straine. Toata lumea stie ca acesta se respecta, asa ca el a ales cea mai de lux companie aeriana si a zis ca va calatori numai cu aceasta. Compania opereaza in $N$ orase mari ale lumii, cu diferite zboruri intre acestea. Mai exact, aceste rute constituie un arbore cu $N$ noduri, cu radacina in nodul $1$, fiecare muchie (cate un zbor in ambele sensuri) avand cate un cost. Cum Pastrama nu este foarte bun la matematica (deoarece el a urmat scola de smecherie), va roaga sa-l ajutati cu urmatoarele $M$ operatii:
 
* $1 x c$ -> costul muchiei de la $x$ la tatal lui $x$ devine $c$ ($2 ≤ N$)
* $2 x y$ -> Pastrama vrea sa plece din nodul $x$ si sa ajunga in nodul $y$. La fiecare pas, daca el se afla intr-un nod anume diferit de $y$, el va alege cu probabilitate egala un vecin al acestui nod si va merge acolo. Pastrama ar vrea sa stie care este costul mediu (expected value) al acestei calatori ($y$ este un stramos al lui $x$).

tip = 1 => update: cost[x] = y
tip = 2 => query: expectedul ca sa ajungi de la x la y (y e stramos al lui x)