Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | treesmen.in, treesmen.out | Sursă | Infoarena Monthly 2014, Runda 5 |
| Autor | Radu Visan, Razvan Salajan | Adăugată de |  Salajan Razvan •vendetta |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Treesmen
Antonio crede că un ultim pas către inima Antoniei este să îi arate acesteia că este un băiat cu intenţii serioase şi din punct de vedere profesional. Acesta o va impresiona cu urmatoarea problema:
Se dă un arbore cu N noduri numerotate de la 1 la N şi rădăcina nodul 1. Iniţial în fiecare nod se află valorea 0. Se mai dau M operaţii, care pot fi de 2 tipuri:
- 0 - x y first ratie: Nodurile de pe lantul x - y se modifica in felul urmator: nodul x creste cu valoarea first, urmatorul nod creste cu valoarea first + 1*ratie, urmatorul cu first + 2*ratie, ... si tot asa pana ajungem la nodul y. Lantul e de forma stramos - nod, adica x va fi tot timpul un stramos de-al nodului y.
- 1 - x: Se cere valoarea curenta din nodul x.
Pentru a isi dovedi maiestria, cu care spera sa o impresioneze pe Antonia, Antonio trebuie sa raspunda la operatiile de tipul 1, in ordinea in care sunt date.
Date de intrare
Fişierul de intrare treesmen.in conţine pe prima linie două numere naturale N şi M despărţite printr-un spaţiu, ce reprezintă, în ordine, numărul de noduri al arborelui şi numărul de operaţii. A doua linie a fişierului conţine N-1 numere naturale despărţite prin câte un spaţiu. Al i-lea număr de pe această linie reprezintă părintele nodului cu indicele i+1. Pe urmatoarele M linii se afla operatiile, sub forma descrisa in enunt.
Date de ieşire
În fişierul de ieşire treesmen.out se vor afisa raspunsurile pentru operatiile de tipul 1 in ordinea primita in fisierul de intrare.
Restricţii
- 1 ≤ N, M ≤ 10^5
- 1 ≤ first, ratie ≤ 10^3
- Daca Antonio rezolva aceasta problema de 100 puncte, Antonia va fi impresionata si vor trai fericiti pana la adanci batraneti!
Exemplu
| treesmen.in | treesmen.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
