Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | defrisare.in, defrisare.out | Sursă | Autumn WarmUp 2020 |
| Autor | Mihai-Cristian Popescu | Adăugată de |  autumnwarmup2020 •autumnwarmup2020 |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Defrisare
Padurea este reprezentata de un set de 
copaci de diferite inaltimi, conectati intre ei de 
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
Fişierul de intrare defrisare.in ...
Date de ieşire
În fişierul de ieşire defrisare.out ...
Restricţii
- Subtaskul 1 de 10 puncte: n <= 20
Subtaskul 2 de 10 puncte: n <= 100000 şi arborele este format dintr-ul nod central de care sunt legate toate celelalte noduri.
Subtaskul 3 de 10 puncte: n <= 100000 şi arborele este binar (fiecare nod are maxim 2 fii)
Subtaskul 4 de 50 de puncte: n <= 100000
Exemplu
| defrisare.in | defrisare.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
Numarul de langa fiecare nod reprezinta inaltimea copacului respectiv.
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. (1 -> 2 -> 4, 3, 5, 6)
2. Copacul 3 cade pe copacul 2 care cade pe copacul 4 iar restul sunt taiati individual. (3 -> 2 -> 4, 1, 5, 6)
