| Fişierul intrare/ieşire: | kdtree.in, kdtree.out | Sursă | Lot Vrancea 2010, Baraj 1 |
| Autor | Cosmin Gheorghe | Adăugată de |  Andrei Misarca •Mishu91 |
| Timp execuţie pe test | 0.275 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
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.
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.
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
Exemplu
| kdtree.in | kdtree.out |
|---|---|
| 6 2 1 2 1 3 1 4 2 5 2 6 | 1 |
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.
