| Fişierul intrare/ieşire: | infestation.in, infestation.out | Sursă | Shumen 2019 Seniori |
| Autor | Encho Mishinev | Adăugată de |  Matteo Verzotti •Matteoalexandru |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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 infestat. 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 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).
Date de intrare
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 pi+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.
Date de ieşire
Î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.
Restricţii
- 1 ≤ N, Q ≤ 3 * 105
Subtaskuri
| Subtask | Puncte | N, Q | Tipuri de evenimente | Restrictii aditionale |
|---|---|---|---|---|
| 1 | 7 | ≤ 2 * 103 | 1, 2, 3, 4 | - |
| 2 | 8 | ≤ 3 * 105 | 1, 4 | - |
| 3 | 10 | ≤ 3 * 105 | 1, 2, 3, 4 | Arborele este generat aleatoriu* |
| 4 | 9 | ≤ 3 * 105 | 1, 3, 4 | - |
| 5 | 23 | ≤ 3 * 105 | 1, 2, 3, 4 | Fiecare nod are maxim 4 fii |
| 6 | 17 | ≤ 105 | 1, 2, 3, 4 | - |
| 7 | 26 | ≤ 3 * 105 | 1, 2, 3, 4 | - |
*Pentru a genera un arbore aleatoriu pentru fiecare nod i il generam pe tatal sau (adica pi) ca un numar intreg aleatoriu in intervalul [1, i - 1].
Exemplu
| infestation.in | infestation.out |
|---|---|
| 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 |
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.
