dominouri

Dominouri

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

Pe o tablă sunt N dominouri. Acestea sunt aşezate sub forma unui arbore. Dacă unele piese de domino sunt lovite cu o forţă destul de mare, ele vor cădea peste o altă piesă (excepţie face piesa 1 care nu cade peste alte piese). Pentru fiecare piesă de domino de pe tablă se cunoaşte câte alte piese trebuie să cadă peste ea pentru a cădea la rândul său, dar şi care sunt piesele care pot să cadă peste aceasta. Mitruţ tocmai a descoperit tabla cu dominouri şi se întreabă care e numărul minim de piese pe care trebuie să le doboare el pentru a face piesa 1 să cadă. Fiindcă Mitruţ are reguli stricte legate de arbori, el îşi dă voie să doboare doar piesele peste care nu are cine să cadă (frunzele din arbore).

Pe o tablă sunt $N$ dominouri. Acestea sunt aşezate sub forma unui arbore. Dacă unele piese de domino sunt lovite cu o forţă destul de mare, ele vor cădea peste o altă piesă (excepţie face piesa $1$ care nu cade peste alte piese). Pentru fiecare piesă de domino de pe tablă se cunoaşte câte alte piese trebuie să cadă peste ea pentru a cădea la rândul său, dar şi care sunt piesele care pot să cadă peste aceasta. Mitruţ tocmai a descoperit tabla cu dominouri şi se întreabă care e numărul minim de piese pe care trebuie să le doboare el pentru a face piesa $1$ să cadă. Fiindcă Mitruţ are reguli stricte legate de arbori, el îşi dă voie să doboare doar piesele peste care nu are cine să cadă (frunzele din arbore).

h2. Cerinţă

h2. Date de intrare

Fişierul de intrare dominouri.in conţine pe prima linie numărul N. Pe următoarele N linii se află câte un număr Ci (1 ≤ i ≤ N).reprezentând câte piese pot să cadă peste piesa i, urmat de Ci numere-indicele pieselor care dacă sunt lovite cad peste piesa i. Ultima linie din fişier conţine N numere naturale Fi(1 ≤ i ≤ N).  Fi reprezintă numărul de piese care trebuie sa cadă pe dominoul i ca acesta să cadă şi el la rândul său. Frunzele din arbore au acest număr egal cu zero.

Fişierul de intrare dominouri.in conţine pe prima linie numărul $N$. Pe următoarele $N$ linii se află câte un număr $C{~i~}$ ({$1$} ≤ $i$ ≤ $N$).reprezentând câte piese pot să cadă peste piesa $i$, urmat de $C{~i~}$ numere-indicele pieselor care dacă sunt lovite cad peste piesa $i$. Ultima linie din fişier conţine $N$ numere naturale $F{~i~}$({$1$} ≤ $i$ ≤ $N$). $F{~i~}$ reprezintă numărul de piese care trebuie sa cadă pe dominoul $i$ ca acesta să cadă şi el la rândul său. Frunzele din arbore au acest număr egal cu zero.

h2. Date de ieşire

h2. Restricţii

•	1 ≤ N ≤ 100 000
•	Fi este întotdeauna mai mic sau egal cu numărul de fii ai nodului(piesei) i.
•	Pentru toate nodurile terminale din arbore Fi = 0.

* $1 ≤ N ≤ 100 000$
* $F{~i~}$ este întotdeauna mai mic sau egal cu numărul de fii ai nodului(piesei) $i$.
* Pentru toate nodurile terminale din arbore $F{~i~}$ = 0.

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

|
|

| 10
  3 2 3 4
  2 5 6
  1 7
  3 8 9 10
  0
  0
  0
  0
  0
  0
  2 1 1 2 0 0 0 0 0 0
| 2

|
h3. Explicaţie

...

Sunt de ajuns două piese pentru a doborâ dominoul 1. Acestea sunt ori 5 şi 7 ori 6 şi 7. Dominoul 7 este folosit pentru răsturnarea lui 3, în timp ce piesa 5 este folosită pentru răsturnarea lui 2. Piesele care fac ca 1 să cadă efectiv sunt 2 şi 3.
 
!problema/dominouri?arb.jpg!

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

5501