Fişierul intrare/ieşire:	pisici.in, pisici.out	Sursă	ad-hoc
Autor	Alexandru Petrescu	Adăugată de	descarc •arhive
Timp execuţie pe test	0.125 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Pisici

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:

1. 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}.
2. 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.
3. 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ă.

Date de intrare

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⁹ si ca 1 ≤ t[i] ≤ i.

Date de ieşire

Î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.

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

Exemplu

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)!

Cum se trimit solutii?