== include(page="template/taskheader" task_id="salvare") ==
Se considera un arbore (graf neorientat, conex si aciclic) cu $N$ varfuri. In nodurile acestui arbore locuiesc oameni, iar muchiile au lungime 1. Se doreste infiintarea in noduri ale arborelui a $K$ puncte de salvare, astfel incat locuitorii arborelui sa fie ajutati cat mai rapid in caz de urgente.
La aparitia unei urgente intr-un anumit nod, o masina a Salvarii pleaca dintr-unul din cele mai apropiate puncte de salvare catre nodul respectiv, pentru a acorda primul ajutor, dupa care se intoarce la punctul de plecare. Timpul de rezolvare a unei urgente este dat de numarul de muchii parcurse de la punctul de salvare la nodul in care a aparut urgenta. Se considera ca pana la intoarcerea salvarii in punctul de plecare nu pot aparea urgente noi.
Sa se stabileasca nodurile in care se vor infiinta puncte de salvare, astfel incat orice urgenta sa fie rezolvabila in timp minim (mai exact, maximul $M$ al timpilor de rezolvare sa fie minim).
Poveste si cerinta...
h2. Date de intrare
Prima linie a fisierului de intrare $salvare.in$ contine numarul intreg $N$, reprezentand numarul de varfuri ale arborelui. A doua linie a fisierului contine numarul intreg $K$, reprezentand numarul de puncte de salvare. Urmatoarele $N-1$ linii contin cate doi intregi distincti $a$ si $b$, separati printr-un spatiu, avand semnificatia ca exista muchie intre varful numerotat cu $a$ si cel numerotat cu $b$.
...
h2. Date de iesire
In fisierul $salvare.out$ veti afisa:
* pe prima linie numarul $M$, maximul timpilor de rezolvare;
* pe a doua linie $K$ numere distincte intre $1$ si $N$, ordonate crescator, nodurile in care se vor infiinta puncte de salvare
...
h2. Restrictii
* $1 ≤ N ≤ 1000$
* $1 ≤ K ≤ 300$
* Varfurile sunt numerotate cu numere distincte intre $1$ si $N$
* Daca exista mai multe solutii, se va afisa una oarecare
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. salvare.in |_. salvare.out |
| 5
2
4 1
1 3
1 2
4 5
| 1
1 4
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
Timpul maxim de rezolvare este 1. Se infiinteaza doua puncte de salvare, in nodurile 1 si 4. Salvarea din 1 rezolva urgentele din 1 in timp 0 si urgentele din 2 si 3 in timp 1. Salvarea din 4 rezolva urgentele din 4 in timp 0 si urgentele din 5 in timp 1. Exista si alte solutii.
...
== include(page="template/taskfooter" task_id="salvare") ==
