Fişierul intrare/ieşire:arborest.in, arborest.outSursăAlgoritmiada 2010, Runda 1
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Arborest

Nectaria are un arbore cu N noduri cu radacina in nodul 1. Din pacate Nectariei nu-i place arborele ei pentru ca este prea adanc. Adancimea unui arbore este egala cu distanta maxima intre radacina si un nod. Nectaria poate face urmatoarea operatie: alege un nod x si apoi schimba tatal lui x in alt nod din arbore (modifica muchia x - tata[x]), dar are grija sa nu creeze cicluri in arbore. Din pacate ea poate face maxim K operatii de acest gen. Nectaria vrea sa stie care este adancimea minima la care poate ajunge arborele facand asupra lui cel mult K operatii de schimbare de tata a unui nod.

Date de intrare

Fişierul de intrare arborest.in va contine pe prima linie N si K reprezentand numarul nodurilor din arbore si respectiv numarul maxim admis de operatii. Pe a doua linie se vor afla N - 1 numere, numarul i reprezentand tatal nodului i + 1 (nodul 1 nu are tata; este radacina).

Date de ieşire

În fişierul de ieşire arborest.out veti afisa un singur numar, adancimea minima la care poate ajunge arborele dupa cel mult K operatii.

Restricţii

  • 1 ≤ N, K ≤ 100 000
  • Atentie: Distanta intre doua noduri x si y din arbore este egala cu numarul de muchii aflate pe drumul intre x si y.

Exemplu

arborest.inarborest.out
11 2
1 1 3 3 4 4 7 2 9 10
3

Explicaţie

Nectaria poate modifica tatal nodului 4 sa devina nodul 1 si tatal nodului 11 sa devina nodul 9. Nu se poate obtine o adancime mai mica.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content