infestation

Infestation

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

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:

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 infestat. Mai multe evenimente se intampla consecutiv, fiecare dintre ele fiind unul din urmatoarele 4 tipuri:

- $"1 X"$ - Nodul $X$ devine infestat

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

- $"3 X"$ - Lora angajeaza profesionisti care sa elibereze nodul $X$ si copiii sai. In concluzie, $X$ si toti succesorii sai *directi* nu mai sunt infestati.

- $"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. Restricţii

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

* $1 ≤ N, Q ≤ 3 * 10^5^$
 
h2. Subtaskuri
 
table(example). |_. Subtask |_. Puncte |_. N, Q |_. Tipuri de evenimente |_. Restrictii aditionale |
| 1 | 7 | ≤ 2 * 10^3^ | 1, 2, 3, 4 | - |
| 2 | 8 | ≤ 3 * 10^5^ | 1, 4 | - |
| 3 | 10 | ≤ 3 * 10^5^ | 1, 2, 3, 4 | Arborele este generat aleatoriu* |
| 4 | 9 | ≤ 3 * 10^5^ | 1, 3, 4 | - |
| 5 | 23 | ≤ 3 * 10^5^ | 1, 2, 3, 4 | Fiecare nod are maxim 4 fii |
| 6 | 17 | ≤ 10^5^ | 1, 2, 3, 4 | - |
| 7 | 26 | ≤ 3 * 10^5^ | 1, 2, 3, 4 | - |
 
*{_Pentru a genera un arbore aleatoriu pentru fiecare nod $i$ il generam pe tatal sau (adica $p{~i~}$) ca un numar intreg aleatoriu in intervalul $[1, i - 1]$_}.

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

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

| 5
1 1 3 3
8
1 3
2 5
4 1
1 1
2 1
4 3
3 1
4 3
| 1 2 1

|
h3. Explicaţie

...

Evenimentele au urmatorul efect:
 
- $"1 3"$ - Nodul $3$ devine infestat.
- $"2 5"$ - Lora foloseste ultrasunet pe nodurile aflate pe lantul de la $1$ la $5$. Acestea sunt nodurile $1$, $3$ si $5$. Nodul $3$ este infestat si singurul vecin al sau fara ultrasunet este nodul $4$. Prin urmare, nodul $3$ nu mai este infestat si nodul $4$ devine infestat.
- $"4 1"$ - Subarborele nodului $1$ este constituit de toate nodurile din arbore. Singurul nod infestat este nodul $4$.
- $"1 1"$ - Nodul $1$ devine infestat.
- $"2 1"$ - Lora foloseste ultrasunet in nodul $1$. Nodurile $2$ si $3$ devin infestate, in timp ce nodul $1$ nu mai este infestat.
- $"4 3"$ - Subarborele nodului $3$ este constituit de nodurile $3$, $4$ si $5$. Din ele, nodurile $3$ si $4$ sunt infestate.
- $"3 1"$ - Nodul $1$ si succesorii sai directi, adica nodurile $1$, $2$ si $3$, nu mai sunt infestate.
- $"4 3"$ - Dintre nodurile $3$, $4$ si $5$, doar nodul $4$ este infestat.

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