==Include(page="template/taskheader" task_id="arbore")==

==Include(page="template/raw")==
 

O firma are $N$ angajati numerotati de la $1$ la $N$. Angajatii sunt ierarhizati sub forma de arbore (graf conex fara cicluri). Astfel, fiecare angajat are exact un sef direct (cu exceptia patronului firmei), iar un anumit angajat poate avea mai multi subordonati directi. Patronul firmei este numerotat cu $1$. Un angajat $A$ este subordonatul unui alt angajat $B$ daca una din urmatoarele conditii este indeplinita:
* $A$ este subordonat direct al lui $B$

h2. Cerinta

Scrieti un program care primeste N, M, structura angajatilor si cele M operatii iar pentru fiecare operatie de tipul 2 afiseaza valoarea ceruta.

Scrieti un program care primeste {$N$}, {$M$}, structura angajatilor si cele $M$ operatii iar pentru fiecare operatie de tipul $2$ afiseaza valoarea ceruta.

h2. Date de Intrare

Fisierul arbore.in contine pe prima linie numerele N si M separate printr-un spatiu.
 
Urmatoarele N - 1 linii contin cate doua numere intregi p si q cu semnificatia ca "exista relatie directa intre angajatul p si angajatul q".
 
Urmatoarele M linii cotin cate o operatie pe linie. Primul numar de pe linie este 1 sau 2, si semnifica tipul operatiei ce va fi descrisa. In cazul unei operatii de tip 1 vor urma numerele p si s, iar in cazul unei operatii de tip 2 va urma un singur numar s.

Fisierul $arbore.in$ contine pe prima linie numerele $N$ si $M$ separate printr-un spatiu.
Urmatoarele $N-1$ linii contin cate doua numere intregi $p$ si $q$ cu semnificatia ca "exista relatie directa intre angajatul $p$ si angajatul {$q$}".
Urmatoarele $M$ linii cotin cate o operatie pe linie. Primul numar de pe linie este $1$ sau {$2$}, si semnifica tipul operatiei ce va fi descrisa. In cazul unei operatii de tip $1$ vor urma numerele $p$ si {$s$}, iar in cazul unei operatii de tip $2$ va urma un singur numar {$s$}.

h2. Date de Iesire

Fisierul arbore.out contine pentru fiecare operatie de tip 2 indicele unui angajat care a primit suma respectiva de bani pana la momentul respectiv. In cazul in care nu exista un asemenea angajat, se cere sa se afiseze -1. Nu are importanta indicele carui angajat il veti afisa, atata timp cat acesta a primit suma s.

Fisierul $arbore.out$ contine pentru fiecare operatie de tip $2$ indicele unui angajat care a primit suma respectiva de bani pana la momentul respectiv. In cazul in care nu exista un asemenea angajat, se cere sa se afiseze {$-1$}. Nu are importanta indicele carui angajat il veti afisa, atata timp cat acesta a primit suma {$s$}.

h2. Restrictii si precizari

&#159; 1 <= N, M <= 100 000
 
&#159; pentru o operatie de tipul 1 avem 1 <= s <= 10
 
&#159; pentru o operatie de tipul 2 avem 0 <= s <= 1 000 000
 
&#159; 50% dintre testele folosite la evaluare nu vor contine mai mult de 100 de operatii de tip 2

* $1 ≤ N, M ≤ 100 000$
* pentru o operatie de tipul $1$ avem $1 ≤ s ≤ 10$
* pentru o operatie de tipul $2$ avem $0 ≤ s ≤ 1 000 000$
* $50%$ dintre testele folosite la evaluare nu vor contine mai mult de $100$ de operatii de tip $2$

h2. Exemplu

arbore.in arbore.out
6 6 2
 
1 2 1
 
1 3 3
 

table(example). |_. arbore.in |_. arbore.out |
| 6 6
1 2
1 3

3 4

3 5

4 6

1 1 1

1 2 4

2 5

2 1

1 3 3

2 4

| 2
1
3 |

 
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/arbore/enunt_files/filelist.xml

==Include(page="template/taskfooter" task_id="arbore")==

932