Revizia anterioară Revizia următoare
| 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 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 ≤ 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. Pastrama ar vrea sa stie care este costul mediu (expected value) al acestei calatori ( 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 ...
Afisati expectedul sub forma p q, unde (p,q) = 1 si E = p / q
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| taristraine.in | taristraine.out |
|---|---|
| 3 2 1 10 1 5 1 2 5 2 2 1 | 5 1 |
Explicaţie
...
