== include(page="template/taskheader" task_id="avele") ==

Un arbore cu rădăcină $T$ se numeşte arbore $AVELE$ dacă, pentru fiecare nod nenul $v$, avem că $v$ are exact doi fii (nu neapărat nenuli), $left_son(v)$ şi $right_son(v)$, iar _înălţimea subarborilor cu rădăcina în cei doi fii diferă cu maxim 1_. (formal, $|height(left_son(v)) - height(right_son(v))| <= 1$, unde $|x|$ denotă valoarea absolută a numărului întreg $x$).

Un arbore cu rădăcină $T$ se numeşte arbore *AVELE* dacă, pentru fiecare nod nenul $v$, avem că $v$ are exact doi fii (nu neapărat nenuli), $left_son(v)$ şi $right_son(v)$, iar _înălţimea subarborilor cu rădăcina în cei doi fii diferă cu maxim 1_. (formal, $|height(left_son(v)) - height(right_son(v))| <= 1$, unde $|x|$ denotă valoarea absolută a numărului întreg $x$).

*Înălţimea* subarborelui cu rădăcina în nodul $v$ este egală cu $0$, dacă şi numai dacă subarborele este vid ($height(0) = 0$), altfel se defineşte după formula $height(v) = 1 + max(height(left_son(v)), height(right_son(v)))$.

*Înălţimea* subarborelui cu rădăcina în nodul $v$ este egală cu $0$, dacă şi numai dacă subarborele este vid (altfel spus, $height(0) = 0$), altfel se defineşte după formula $height(v) = 1 + max(height(left_son(v)), height(right_son(v)))$.
 
h2. Cerinţă
 
Se dă un *arbore binar* cu rădăcina în nodul 1. Să determine costul minim pentru a-l transforma într-un arbore *AVELE*. Operaţiile posibile sunt:
 
* Ştergerea unei frunze de oriunde din arbore (cu costul $cost_rem$);
* Adăugarea unei frunze oriunde în arbore (cu costul $cost_add$).

h2. Date de intrare

Fişierul de intrare $avele.in$ ...

Fişierul de intrare $avele.in$ conţine pe prima linie numerele naturale $N$, $cost_add$, $cost_rem$, iar pe următoarele două linii, câte două numere naturale,
reprezentând $left_son(i)$, respectiv $right_son(i)$, pentru fiecare nod $i$ din arbore.

h2. Date de ieşire

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$
* $0 ≤ left_son(i), right_son(i) ≤ N$
* $1 ≤ cost_add, cost_rem ≤ 1.000.000.000$

h2. Exemplu
table(example). |_. avele.in |_. avele.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 10 5
  2 0
  3 0
  0 0
| 5
|
| 3 2 8
  0 2
  3 0
  0 0
| 2
|
| 3 1 1
  2 3
  0 0
  0 0
| 0

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="avele") ==