== include(page="template/taskheader" task_id="pisici") ==
Poveste şi cerinţă...
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.
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:
# 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ă.
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).
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") ==
