Fişierul intrare/ieşire:taristraine.in, taristraine.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorChichirim GeorgeAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test1.2 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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 Ti si Ci 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 ≤ 105
  • 1 ≤ costul unei muchii ≤ 106
  • 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

taristraine.intaristraine.out
3 2
1 10
1 7
1 2 5
2 2 1
5 1

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?