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

Poveste şi cerinţă...

Vila Lorei este invadata de sobolani. Din fericire, putem descrie camerele din vila Lorei ca si un arbore cu radacina in nodul $1$, care are $N$ noduri. Initial, niciun nod nu este infectat. Mai multe evenimente se intampla consecutiv, fiecare dintre ele fiind unul din urmatoarele 4 tipuri:
 
- $"1 X"$ - Nodul $X$ devine infestat
- $"2 X"$ - Lora vrea sa elimine soarecii din nodurile de pe lantul de la nodul $1$ la nodul $X$ (inclusiv) folosind ultrasunet pe toti simultan. Daca ultrasunetul este folosit pe un nod infestat, soarecii din el se imprastie, iar fiecare din vecinii sai directi, *in care ultrasunetul nu este folosit la momentul actual*, devine infestat. Nodurile in care folosim ultrasunetul se opresc din a fi infestate. Dupa ce soarecii s-au mutat, ultrasunetul este oprit, adica nodurile eliberate pot fi infestate din nou, in viitor.
- $"3 X"$ - Lora angajeaza profesionisti care sa elibereze nodul $X$ si copiii sai. In concluzie, $X$ si toti succesorii sai *directi* nu mai sunt infectati.
- $"4 X"$ - Lora doreste sa stie numarul total de noduri infestate din subarborele nodului $X$.
 
Subarborele nodului $X$ este definit ca si setul de noduri care il contin pe $X$, precum si toti succesorii sai directi sau indirecti (vezi exemplul pentru mai multe informatii).

h2. Date de intrare

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

Fişierul de intrare $infestation.in$ va contine pe prima linie numarul natural $N$ - numarul de noduri din arbore. A doua linie contine $N - 1$ numere, al $i$-lea fiind $p{~i+1~}$ - parintele nodului $i + 1$. A treia linie contine numarul de evenimente $Q$. Urmatoarele $Q$ linii contin cate doua numere intregi, ce reprezinta cate un eveniment in una din formatele mentionate anterior.

h2. Date de ieşire

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

În fişierul de ieşire $infestation.out$ se va afisa pentru fiecare eveniment de tipul $4$ cate un singur numar pe o linie - numarul de noduri infestate din subarbore.

h2. Restricţii