arborest

Arborest

== include(page="template/taskheader" task_id="arborest") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $arborest.in$ ...

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).

h2. Date de ieşire

În fişierul de ieşire $arborest.out$ ...

Î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.

h2. 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$.

h2. Exemplu
table(example). |_. arborest.in |_. arborest.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 11 2
1 1 3 3 4 4 7 2 9 10
| 3

|
h3. 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.

== include(page="template/taskfooter" task_id="arborest") ==

4305