tree

Tree

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

Poveste şi cerinţă...

Se da un arbore cu $N$ noduri. Asupra lui se pot efectua urmatoarele operatii:
 
* se adauga o muchie intre doua noduri
* se sterge o muchie intre doua noduri
 
Trebuie sa determinam numarul minim de operatii pe care trebuie sa le efectuam astfel incat sa transformam arborele intr-un ciclu.

h2. Date de intrare

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

Fişierul de intrare $tree.in$ contine pe prima linie {$N$}, numarul de noduri din arbore. Cea de a doua linie contine $N$ numere naturale. Al $i$-lea numar de pe aceasta linie reprezinta parintele nodului $i$ in arbore. Daca acest numar este $0$ atunci nodul corespunzator este considerat radacina.

h2. Date de ieşire

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

În fişierul de ieşire $tree.out$ se va afisa numarul minim de operatii ce trebuiesc efectuate pentru a obtine transformarea dorita.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 200 000$

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

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

|3
0 1 1
|1
|

h3. Explicaţie

...

Se va adauga o muchie intre nodurile $2$ si $3$ si astfel se va obtine un ciclu.

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

4689