Fişierul intrare/ieşire:	taristraine.in, taristraine.out	Sursă	Concursul National de Informatica "Adolescent Grigore Moisil" 18
Autor	Chichirim George	Adăugată de	AGMInformatica •AGMinformatica
Timp execuţie pe test	0.6 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tari Straine

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 scoala 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 ≤ x ≤ 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, platind costul aferent desigur. Va repeta acest lucru pana va ajunge in nodul y. Pastrama ar vrea sa stie care este costul mediu (expected value) al acestei calatorii ( y este un stramos al lui x )

Date de intrare

Fişierul de intrare taristraine.in contine pe prima linie numerele naturale N si M, cu semnificatiile din enunt. Pe urmatoarele N-1 linii se afla cate doua numere naturale T_i si C_i care reprezinta tatal nodului i si costul muchiei respective ( 2 ≤ i ≤ N ). Pe urmatoarele M linii se afla cele M operatii descrise in enunt.

Date de ieşire

În fişierul de ieşire taristraine.out se vor afla raspunsurile la operatiile de tipul 2, fiecare pe cate o linie, in ordinea in care acestea apar in fisierul de intarare. Afisati raspunsurile sub forma p q, unde raspunsul (expected value) este egal cu p / q si cel mai mic multiplu comun al lui p si q este 1.

Restricţii

• 1 ≤ N, M ≤ 10⁵
• 1 ≤ costul unei muchii ≤ 10⁶
• La operatia de tipul 2, nodul y este un stramos al nodului x
• Pastrama plateste pentru placerile sale, iar de aceea compania de lux pe care si-a ales-o detine numai avioane americane

Exemplu

Explicaţie

Prima operatie: costul muchiei 1 -> 2 devine 5.
A doua operatie: singurul vecin al nodului 2 este 1, deci singura optiune este sa mergi acolo. Deci, costul mediu este 5.

Cum se trimit solutii?