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 p r: cu x strămoş al lui y; nodurile de pe lanţul x - y cresc cu valoarea termenilor progresiei arimetice cu primul termen egal cu p şi raţie r. Mai exact nodul x creste cu valoarea p, urmatorul nod creste cu valoarea p+r, urmatorul nod creste cu valoarea p+2*r, etc.
- 1 x: se cere valoarea curentă 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 un numar natul N, ce reprezintă, numărul de noduri al arborelui. 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 urmatoarea linie se afla un numar natural M, ce reprezinta, numarul de operatii.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
...
