Problem 1825: 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 probabilitate $p_{x,y}$ . Î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 are valoarea maximă $q$ pe care o poate avea $q_x$ este minimizată.

Protocol de interacțiune

Concurentul va implementa o singură funcție, solve, cu următoarea semnătură:

long long solve (int n, std::vector<int> t, std::vector<int> v);

Parametrii acestei funcții au următoarea semnificație:

$n$ reprezinta numărul de noduri din arbore. Acestea sunt numerotate de la $1$ la $n$ .
$t$ conține $n-1$ elemente cu semnificația că există muchie între $i + 2$ și $t[i]$ pentru $i = 0, 1, ..., n-2$ .
$v$ conține tot $n - 1$ elemente cu semnificația că $p_{i+2,t[i]} = 2^{-v[i]}$ . Aceste numere sunt numere întregi pentru a evita erorile de precizie. Se garantează că $0 \le v[i] \le 10^9$ .

Funcția va întoarce 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.

Concurentul NU va implementa o funcție main.

Subtask 1 (6 puncte)

$N \le 8$

Subtask 2 (9 puncte)

$N \le 25$
Se garantează că pentru oricare nod $i = 1, 2, ..., n$ , există fie $2$ valori, fie nicio valoare $j$ în $\{1, 2, ..., n\}$ cu proprietatea ca $t[j] = i$ .

Subtask 3 (8 puncte)

$N \le 100\ 000$
Fiecare nod are grad maxim $2$ .

Subtask 4 (18 puncte)

$N \le 50$

Subtask 5 (19 puncte)

$N \le 700$

Subtask 6 (7 puncte)

$N \le 100\ 000$
Se garantează că pentru oricare nod $i = 1, 2, ..., n$ , există fie $2$ valori, fie nicio valoare $j$ în $\{1, 2, ..., n\}$ cu proprietatea ca $t[j] = i$ .

Subtask 7 (16 puncte)

$N \le 100\ 000$
Toate probabilitățile corespunzătoare muchiilor sunt egale între ele.

Subtask 8 (17 puncte)

$N \le 100\ 000$

Exemple

Input

Output