Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-08-30 12:07:49.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:defrisare.in, defrisare.outSursăAutumn WarmUp 2020
AutorMihai-Cristian PopescuAdăugată deautumnwarmup2020autumnwarmup2020 autumnwarmup2020
Timp execuţie pe test0.175 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Defrisare

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

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.

Date de intrare

Pe prima linie se va afla numărul 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.

Date de ieşire

Fişierul de ieşire va conţine o singura linie pe care se afla raspunsul la întrebare.

Restricţii

  • Subtaskul 1 de 10 puncte:   3 \le n \le 20
  • Subtaskul 2 de 10 puncte:   3 \le n \le 10^{5} şi arborele are forma unei linii (există exact 2 noduri cu grad 1 şi n - 2 cu grad 2)
  • Subtaskul 3 de 10 puncte:   3  \le n \le 10^{5} şi arborele este format dintr-un nod central de care sunt legate toate celelalte noduri
  • Subtaskul 4 de 20 puncte:   3  \le n \le 10^{5} şi arborele este binar (fiecare nod are maxim doi fii)
  • Subtaskul 5 de 50 de puncte:  3  \le n \le 10^{5}

Exemplu

defrisare.indefrisare.out
6
10 5 7 4 1 1
1 2 2
2 3 6
2 4 3
4 5 9
4 6 5
4

Explicaţie

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

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?