== 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':https://hollywoodp.wpengine.com/wp-content/uploads/2013/10/loan-oak-tree.jpg 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$ separate prin câte un spaţiu, iar pe următoarele $N$ 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
În fişierul de ieşire $avele.out$ ...
Fişierul de ieşire $avele.out$ trebuie să conţină un singur număr natural, reprezentând costul minim pentru a transforma arborele într-unul *AVELE*.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $0 ≤ left_son(i), right_son(i) ≤ N$
* $1 ≤ cost_add, cost_rem ≤ 1.000.000.000$
* $Se garantează că datele de intrare sunt valide pentru un arbore binar cu rădăcina în nodul 1.$
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") ==
== include(page="template/taskfooter" task_id="avele") ==
