Fişierul intrare/ieşire:kdtree.in, kdtree.outSursăLot Vrancea 2010, Baraj 1
AutorCosmin GheorgheAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test0.55 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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.inkdtree.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content