| Fişierul intrare/ieşire: | avele.in, avele.out | Sursă | FMI No Stress 8 |
| Autor | Lucian Bicsi | Adăugată de |  Fmi no stress 2018 •fminostress2018 |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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).
Î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))).
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).
Date de intrare
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.
Date de ieşire
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.
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.
Exemplu
| avele.in | avele.out |
|---|---|
| 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 |
