== include(page="template/taskheader" task_id="neapuiu") ==
Poveste şi cerinţă...
_“Una e să te spargi în figuri, şi alta e să spargi figuri”_
Lui $Nea Puiu$ îi place foarte mult să spargă figuri. În cazul de faţă, figurile pe care vrea să le spargă sunt arbori cu $N$ noduri care au rădăcina fixată (un arbore reprezintă un graf neorientat, conex şi aciclic). Prin spargerea unui arbore se înţelege tăierea unei muchii a acestuia, fapt ce cauzează ca toate nodurile care nu mai sunt conectate cu rădăcina arborelui să se desprindă de acesta. Înainte de a da lovitura, Nea Puiu a studiat cu atenţie proprietăţile arborilor şi a definit adâncimea unui subarbore ca fiind cea mai mare distanţă dintre rădăcina subarborelui şi o frunză a acestuia. Fiindcă Nea Puiu nu doreşte să lase multe dovezi după acţiunile sale, el doreşte să răspundă la întrebări de forma: _”În câte moduri poate tăia o muchie din subarborele cu rădăcina în nodul $x$ astfel încât după taiere noua adâncime a subarborelui să fie aceeaşi cu adâncimea de dinainte?”_. Totuşi, $Nea Puiu$ este un profesionist, aşa că se întreabă ce s-ar întampla dacă arborele s ar modifica între diverse întrebări. Aşadar, pot exista două evenimente de modificare a arborelui: fie se şterge o anumită frunză a acestuia, fie se adaugă un nod nou, legat de unul dintre nodurile deja existente în arbore.
h2. Cerinta
Deoarece $Nea Puiu$ este nevoit să se ocupe de contribuţiile la gaze, voi trebuie, dându-se arborele iniţial şi $M$ operaţii de forma celor descrise mai sus, să răspundeţi la întrebările acestuia!
h2. Date de intrare
Fişierul de intrare $neapuiu.in$ ...
Fişierul de intrare $neapuiu.in$ conţine două numere naturale: $N$, numărul de noduri din arbore şi $M$, numărul de operaţii ce se vor efectua.
Următoarele $N – 1$ linii descriu muchiile arborelui. Fiecare linie conţine două numere naturale, $x$ şi $y$, separate printr-un spaţiu, reprezentând faptul ca există o muchie de la $x$ la $y$ în arbore.
Următoarele $M$ linii descriu operaţiile efectuate. Fiecare linie este formată din numere naturale şi poate avea unul dintre următoarele formate:
* $0 x y$ – se adaugă nodul cu indicele $y$ ca fiu al nodului cu indicele $x$ ; se garantează că nu a mai existat niciun nod în arbore cu indicele $y$ până în momentul de faţă
* $1 x$ – se şterge nodul cu indicele $x$ – se garantează că nodul $x$ este frunză în arborele curent
* $2 x$ – trebuie să răspundeţi la întrebarea : _”În câte moduri pot tăia o muchie din subarborele cu rădăcina în nodul $x$ astfel încât după taiere noua adâncime a subarborelui să fie aceeaşi cu adâncimea de dinainte?”_
h2. Date de ieşire
În fişierul de ieşire $neapuiu.out$ ...
Fişierul de ieşire $neapuiu.out$ va trebui să conţina răspunsurile la întrebările din fişierul de intrare, câte unul pe linie.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 100.000$
* $radacina arborelui este nodul 1; se garanteaza că acest nod nu va fi şters$
* $se garantează că o data ce un nod este şters din arbore, nu va mai exista niciun alt nod adaugat cu acelaşi indice$
* $se garantează că nu vor exista două noduri cu acelaşi indice în arbore$
h2. Exemplu
table(example). |_. neapuiu.in |_. neapuiu.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 9 14
1 2
1 6
2 3
2 4
4 5
6 7
6 8
6 9
2 1
2 2
0 3 10
2 2
2 6
1 8
2 6
0 9 11
0 11 12
2 6
0 7 13
1 12
2 6
2 5
| 5
1
4
3
2
1
4
0
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="neapuiu") ==
