Fişierul intrare/ieşire:	neapuiu.in, neapuiu.out	Sursă	Lot Mehedinți 2015 - Baraj 4 Seniori
Autor	Andrei Ciocan, Andrei Parvu, Vlad Ionescu	Adăugată de	Tatomir Alex •atatomir
Timp execuţie pe test	0.25 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Neapuiu

“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.

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!

Date de intrare

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?”

Date de ieşire

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.

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

Exemplu

Cum se trimit solutii?