Fişierul intrare/ieşire:avele.in, avele.outSursăFMI No Stress 8
AutorLucian BicsiAdăugată defminostress2018Fmi no stress 2018 fminostress2018
Timp execuţie pe test3 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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.inavele.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?