Diferente pentru problema/taristraine intre reviziile #23 si #34

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="taristraine") ==
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:
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. Pastrama ar vrea sa stie care este costul mediu (expected value) al acestei calatori **( $y$ este un stramos al lui $x$ )**.
* $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$ )**
h2. 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.
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.
h2. Date de ieşire
* $1 ≤ N, M ≤ 10^5^$
* $1 ≤ costul unei muchii ≤ 10^6^$
* **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
h2. Exemplu

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.