h2. Date de intrare

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

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

h2. Date de ieşire

h2. Restricţii
* 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 (exista 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-ul nod central de care sunt legate toate celelalte noduri

* 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>

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!

Exista doua moduri de a obţine numar 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 taiati 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 taiati individual. (<tex>3 -> 2 -> 4;</tex> <tex>1;</tex> <tex>5;</tex> <tex>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") ==