== include(page="template/taskheader" task_id="kdtree") ==
Kilikinei îi plac mult arborii. De data aceasta ea a definit un $KDtree$ ca fiind un arbore pentru care distanţa între oricare două noduri este mai mică sau egală cu $K$. Acum, Kilikina are un arbore cu $N$ noduri şi se întreabă care este numărul minim de muchii pe care trebuie să le taie din arbore, astfel încât toţi arborii rămaşi să fie $KDtrees$.
Scrieţi un program care poate răspunde la întrebarea Kilikinei.
Poveste şi cerinţă...
h2. Date de intrare
Pe prima linie a fişierului de intrare $kdtree.in$ se vor afla două numere naturale $N$ şi $K$ având semnificaţiile din enunţ. Următoarele $N-1$ linii vor conţine câte două numere $x$ şi $y$, reprezentând faptul că există o muchie între nodurile $x$ şi $y$ din arbore.
Fişierul de intrare $kdtree.in$ ...
h2. Date de ieşire
În fişierul de ieşire $kdtree.out$ veţi afişa un singur număr reprezentând numărul minim de muchii ce trebuiesc tăiate din arbore astfel încât toţi arborii rămaşi să fie $KDtrees$.
În fişierul de ieşire $kdtree.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 200.000$
* $1 ≤ K ≤ 200.000$
* Pentru $40%$ din teste $N ≤ 1.000$ şi $K ≤ 50$
* Pentru $70%$ din teste $N ≤ 100.000$ şi $K ≤ 100$
* Distanţa între două noduri $x$ şi $y$ din arbore este egală cu numărul de muchii aflate pe drumul dintre $x$ şi $y$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. kdtree.in |_. kdtree.out |
|6 2
1 2
1 3
1 4
2 5
2 6
| 1
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Se va tăia o singură muchie, muchia $1-2$, astfel încât cei doi arbori rămaşi formaţi din nodurile $(1, 3, 4)$ şi $(2, 5, 6)$ au distanţa între oricare două noduri mai mică sau egală cu $K = 2$.
...
== include(page="template/taskfooter" task_id="kdtree") ==
