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

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.

Cum se trimit solutii?