== include(page="template/taskheader" task_id="pisici") ==
_Nota: Surse si teste la /problema/impreuna_
Se dă un arbore cu $N ≥ 2$ noduri şi probabilităţi $p$ pe muchii. Pe muchia de la nodul $x$ la $y$ se găseşte probabilitatea $p{~x, y~}$ cu $0 < p{~x, y~} ≤ 1$.
În fiecare nod se află câte o pisică flămândă. Pe fiecare muchie se alfă câte o plăcintă gustoasă, toată numai şoricei, whiskas, lăptic, etc. Toate plăcintele sunt iniţial acoperite, practic invizibile pisicuţelor.
Se da un arbore cu $N$ noduri si probabilitati $P[muchie]$ pe muchii. In fiecare nod se afla cate o pisica flamanda. Pe fiecare muchie se alfa cate o placinta gustoasa, toata numai soricei, wiskas, laptic, etc. Toate placintele sunt initial acoperite, practic invizibile pisicutelor.
Plăcintele vor fi dezvelite pe rând şi bine-cunoscutul nostru personaj, Marcel, are onoarea de a stabili ordinea în care plăcintele vor fi arătate pisicuţelor. Atunci când plăcinta de pe muchia de la nodul $x$ la nodul $y$ este dezvelită, se întâmplă una dintre următoarele:
Marcel stabileste o ordine in care se descopere placintele, pe rand. Atunci cand o placinta este descoperita, daca
# Dacă niciuna dintre pisicile de la nodurile $x$ sau $y$ nu au mâncat încă plăcintă, fie pisicile se vor înţelege şi vor mânca împreună plăcinta de pe muchie, fie se vor certa şi o vor răsturna. Probabilitatea ca cele două să *nu* mănânce amândouă va fi de $p{~x, y~}$.
# Dacă exact una dintre pisici a mâncat deja, acelei pisici îi va fi lene să se mai mişte din nodul ei şi o va lasă (cu generozitate) pe cealaltă să mănânce în linişte şi pace.
# Dacă ambele pisici au mâncat deja, mâncarea va rămâne neatinsă.
# niciuna din pisici nu a mancat inca placinta, au probabilitate $P[muchie]$ sa se inteleaga bine si sa manance amandoua pana se satura. Dar au probabilitate $1 - P[muchie]$ sa rastoarne mancarea, sa arunce cu cocoloase una intr-alta (scuzati violenta) si sa se tavaleasca in resturi, dar nu vor manca.
# exact una din pisici a mancat deja, ii va fi lene sa mai miste din nodul ei si o va lasa pe cealalta sa manance in pace.
# ambele pisici au mancat deja, mancarea va ramane neatinsa.
După ce toate plăcintele au fost descoperite, e clar că fiecare pisică $x$ va avea o probabilitate $q{~x~}$ să fi râmas flămândă (respectiv $1 - q{~x~}$ să fi mâncat).
Dupa ce a descoperit toate placintele, e clar ca fiecare pisica are o probabilitate $Q[pisica]$ sa fi mancat (respectiv $1 - Q[pisica]$ sa fi ramas falamanda).
Ajutati-l pe Marcel sa gaseasca o ordine prin care:
* Probabilitatea ca vreo pereche de pisici sa lase mancarea deoparte pentru a se cunoaste mai bine (scenariul $(3)$ ) sa fie $0$.
* $min(Q[i])$ sa fie maxim.
Afisati acest $min(Q[i])$ maxim obtinut.
Ajutaţi-l pe Marcel să găsească o ordine a dezvelirii plăcintelor în care scenariul 3 (dintre cele descrise mai sus) *NU se poate întâmpla*, şi pentru care valoarea maximă $q$ pe care o poate avea $q{~x~}$ este minimizată.
h2. Date de intrare
Fişierul de intrare $pisici.in$ ...
Fişierul de intrare $pisici.in$ contine, pe prima linie, numarul $n$. Nodurile din arbore sunt numerotate cu numere de la $1$ la $n$. Pe a doua linie se afla $n - 1$ numere, reprezentand sirul $t$ (sa notam cu $t[i]$ al $i$-ulea dintre aceste numere), cu semnificaţia că există muchie între $i + 1$ şi $t[i]$ pentru $i = 1, 2, ... n - 1$. Pe a treia linie se afla $n - 1$ numere, reprezentand sirul $v$, cu semnificaţia că $p{~i+1, t[i]~} = 2^-v[i]^$. *Aceste numere sunt numere întregi pentru a evita erorile de precizie*. Se garantează că $0 ≤ v[i] ≤ 10^9^$ si ca $1 ≤ t[i] ≤ i$.
h2. Date de ieşire
În fişierul de ieşire $pisici.out$ ...
În fişierul de ieşire $pisici.out$ se va afla un număr întreg $r$, cu proprietatea ca probabilitatea $q$ cerută în enunţ să satisfacă $q = 2^-r^$. Numărul acesta se poate demonstra că este mereu întreg.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 50.000$
* $Subtask +Stay Home+, 6 puncte: N ≤ 8$
* $Subtask +Relatives Only+, 9 puncte: N ≤ 25$ si se garantează că pentru oricare nod $i = 1, 2, ... n$, există fie 2 valori, fie nicio valoare $j$ în ${1, 2, ..., n - 1}$ cu proprietatea ca $t[j] = i$.
* $Subtask +At the Airport+, 8 puncte:$ gradul fiecarui nod este maxim 2.
* $Subtask +Camp Isolation+, 18 puncte: N ≤ 50$
* $Subtask +Trapped in School+, 19 puncte: N ≤ 700$
* $Subtask +Family Reunion+, 7 puncte:$ Se garantează că pentru oricare nod $i = 1, 2, ... n$, există fie 2 valori, fie nicio valoare $j$ în ${1, 2, ..., n - 1}$ cu proprietatea ca $t[j] = i$.
* $Subtask +Corporation Party+, 16 puncte:$ toate probabilitatile muchiilor sunt egale
* $Subtask +Town Quarantine+, 17 puncte:$ fara alte garantii
h2. Exemplu
table(example). |_. pisici.in |_. pisici.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 5
1 1 3 1
1 2 1 2
| 3
|
| 8
1 1 2 1 4 6 1
793356 1666576 7158429 2321928 2158429 1035046 1852042
| 7951785
|
h3. Explicaţie
...
În primul exemplu, ordinea dezvelirii plăcintelor de pe muchie este: (1 3), (1 2), (3 4), (1 5).
În al doilea exemplu, exista o ordine pentru care răspunsul ar fi fost mai mic decat cel din exemplu, numai că aceasta presupunea ca sa fi fost posibil ca două pisici să refuze ambele plăcinta dintre ele (scenariul 3, interzis)!
== include(page="template/taskfooter" task_id="pisici") ==
