Fişierul intrare/ieşire:arbore.in, arbore.outSursăpreONI 2006 Runda Finala
AutorDaniel PasailaAdăugată de
Timp execuţie pe test0.8 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Arbore

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
  • A este unul dintre subordonatii unui alt subordonat de-al lui B

Datorita profiturilor foarte mari obtinute de firma, angajatii vor primi anumite sume de bani drept bonus. Pentru a avea o evidenta stricta, contabilul firmei trebuie sa efectueze M operatii de doua tipuri:

  1. dandu-se p si s, toti subordonatii nodului p (inclusiv nodul p) vor primi suma de bani s
  2. dandu-se un numar s, el trebuie sa afle un angajat care a primit pana la momentul respectiv suma s

Mentionam ca unii angajati pot fi recompensati de mai multe ori, iar altii pot sa nu primeasca nimic.

Cerinta

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

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.

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.

Restrictii si precizari

  • 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

Exemplu

arbore.inarbore.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content