Fişierul intrare/ieşire:tree.in, tree.outSursăAlgoritmiada 2010, Runda 4
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.2 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tree

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.

Date de intrare

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.

Date de ieşire

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

Restricţii

  • 1 ≤ N ≤ 200 000

Exemplu

tree.intree.out
3
0 1 1
1

Explicaţie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content