Tree

Problema cere de fapt o acoperire a arborelui dat cu numar minim de drumuri. O acoperire inseamna ca fiecare nod al arborelui apartine exact unui drum. Daca numarul de drumuri din acoperirea optima este X, atunci raspunsul va fi 2*X-1 deoarece sunt necesare X-1 operatii de stergere pentru a separa drumurile in arbore si inca X operatii de adaugare pentru a conecta drumurile astfel incat sa se formeze un ciclu (primul drum va fi conectat cu al doilea printr-o muchie, al doilea cu al treilea, etc.).

Problema acoperirii cu drumuri pentru un arbore se poate rezolva fie prin metoda greedy, fie prin metoda programarii dinamice, ambele abordari avand complexitate liniara in numarul de noduri. Vom descrie abordarea de tip greedy.

Facem o parcurgere DF din nodul radacina. La fiecare pas din DF avem urmatoarele cazuri:

• in nodul curent i se unesc mai multe fire (drumuri simple). Daca numarul de fire va fi P, vom adauga la solutie P-1 drumuri si vom elimina subarborele cu radacina in i. Primul drum va fi de la capatul primului fir la capatul celui de-al doilea, iar celelalte drumuri vor fi formate din nodurile dintre capatul unui fir si un fiu al lui i.
• nodul i este continuarea unui fir (are un singur fiu neeliminat). In acest caz nu adaugam nimic la numarul total de drumuri pentru ca s-ar putea sa unim acest fir mai sus in arbore.

Daca in final ajungem in radacina cu un singur fir, adaugam 1 la raspuns.

Aceasta abordare este foarte simplu de implementat si obtine punctajul maxim.