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

Padurea este reprezentata de un set de <tex> n</tex> copaci de diferite inaltimi, conectati intre ei de <tex> n-1</tex> drumuri de diferite lungimi. Mergand de-alungul drumurilor se poate ajunge de la oricare copac la oricare alt copac.

Personajul nostru principal, Alex, s-a pierdut într-o pădure şi a decis că singurul mod de a ieşi din pădurea respectivă este de a o defrişa complet.

Alex poate dobori orice copac vrea, iar aceasta actiune va avea costul 1. Odata doborit un copac, acesta trebuie sa cada pe unul din drumurile de care este conectat. Daca inaltimea copacului este strict mai mare decat lungimea drumului si copacul de la celalalt capat al drumului nu a cazut inca, acesta va fi de asemenea doborit fara niciun cost suplimentar. Acest copac va cadea si va putea dobori la randul lui alt copac de care este legat si asa mai departe.

Pădurea este reprezentată de un set de <tex> N</tex> copaci de diferite înălţimi, conectaţi între ei de <tex> N - 1</tex> drumuri de diferite lungimi astfel încât mergând de-alungul drumurilor se poate ajunge de la oricare copac la oricare alt copac.
 
Alex poate doborî orice copac vrea, iar această acţiune îl va costa un punct de energie. Odată doborât un copac, acesta trebuie să cadă pe unul din drumurile de care este conectat. Dacă înălţimea copacului este strict mai mare decât lungimea drumului şi copacul de la celălalt capăt al drumului nu a căzut încă, acesta va fi de asemenea doborât fără niciun cost suplimentar. Acest copac va cădea şi va putea doborî la randul lui alt copac de care este legat şi aşa mai departe. De asemenea Alex poate doborî mai mulţi copaci în acelaşi timp indiferent de poziţia acestora şi poate să aleagă pentru orice copac direcţia în care va pica. Deoarece vrea să consume cât mai puţină energie Alex vă roagă să găsiţi numărul minim posibil de puncte de energie necesar pentru a doborî toţi copacii.

h2. Date de intrare

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

Pe prima linie se va afla numărul de copaci <tex>N</tex>.
Pe a doua linie se vor afla <tex>N</tex> valori, al i-lea număr reprezentând înălţimea copacului <tex>i</tex>.
Următoarele <tex>N - 1</tex> linii vor conţine câte un triplet <tex>(X, Y, L)</tex> cu semnificaţia că există un drum de lungime <tex>L</tex> între copacii <tex>X</tex> şi <tex>Y</tex>.

h2. Date de ieşire

În fişierul de ieşire $defrisare.out$ ...

Fişierul de ieşire va conţine o singură linie pe care se afla răspunsul cerut.

h2. Restricţii

* Subtaskul <tex>1</tex> de <tex>10</tex> puncte:  <tex>n \le 20</tex>
* Subtaskul <tex>2</tex> de <tex>10</tex> puncte: <tex> n \le 10^{5} </tex> şi arborele este format dintr-ul nod central de care sunt legate toate celelalte noduri
* Subtaskul <tex>3</tex> de <tex>10</tex> puncte: <tex> n \le 10^{5} </tex> şi arborele este binar (fiecare nod are maxim doi fii)
* Subtaskul <tex>4</tex> de <tex>50</tex> de puncte: <tex> n \le 10^{5} </tex>

* <tex> L \le 10^{9} </tex>
* <tex> H[i] \le 10^{9} </tex> <tex>\forall i \in [1, N] </tex>
* Subtaskul <tex>1</tex> de <tex>10</tex> puncte:    <tex> 3 \le n \le 20</tex>
* Subtaskul <tex>2</tex> de <tex>10</tex> puncte:    <tex> 3 \le n \le 10^{5} </tex> şi arborele are forma unei linii (există exact <tex>2</tex> noduri cu grad <tex>1</tex> şi <tex>n - 2</tex> cu grad <tex>2</tex>)
* Subtaskul <tex>3</tex> de <tex>10</tex> puncte:    <tex> 3  \le n \le 10^{5} </tex> şi arborele este format dintr-un nod central de care sunt legate toate celelalte noduri
* Subtaskul <tex>4</tex> de <tex>20</tex> puncte:    <tex> 3  \le n \le 10^{5} </tex> şi arborele este binar (fiecare nod are maxim doi fii)
* Subtaskul <tex>5</tex> de <tex>50</tex> de puncte: <tex> 3  \le n \le 10^{5} </tex>

h2. Exemplu

h3. Explicaţie

Numarul de langa fiecare nod reprezinta inaltimea copacului respectiv.

Numărul de lângă fiecare nod reprezintă înălţimea copacului respectiv.

!defrisare?EXPLICATIE.png!

!problema/defrisare?EXEMPLU.png!

Exista doua moduri de a obţine numar minim de operaţii:
1. Copacul 1 cade pe copacul 2 care cade pe copacul 4 iar restul sunt taiati individual. (<tex>1 -> 2 -> 4,</tex> <tex>3,</tex> <tex>5,</tex> <tex>6 </tex>)
2. Copacul 3 cade pe copacul 2 care cade pe copacul 4 iar restul sunt taiati individual. (<tex>3 -> 2 -> 4, 1, 5, 6 </tex>)

Există două moduri de a obţine un număr minim de operaţii:
1. Copacul <tex>1</tex> cade pe copacul <tex>2</tex> care cade pe copacul <tex>4</tex> iar restul sunt tăiaţi individual. (<tex>1 -> 2 -> 4;</tex> <tex>3;</tex> <tex>5;</tex> <tex>6 </tex>)
2. Copacul <tex>3</tex> cade pe copacul <tex>2</tex> care cade pe copacul <tex>4</tex> iar restul sunt tăiaţi individual. (<tex>3 -> 2 -> 4;</tex> <tex>1;</tex> <tex>5;</tex> <tex>6 </tex>)

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