Fişierul intrare/ieşire:treesmen.in, treesmen.outSursăInfoarena Monthly 2014, Runda 5
AutorRadu Visan, Razvan SalajanAdăugată devendettaSalajan Razvan vendetta
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 următoarea problemă:

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ă valoarea 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 creşte cu valoarea p, următorul nod creşte cu valoarea p+r, următorul nod creşte cu valoarea p+2*r, etc.
  • 1 x: se cere valoarea curentă din nodul x.

Pentru a-şi dovedi măiestria, cu care speră să o impresioneze pe Antonia, Antonio trebuie să raspundă la operaţiile de tipul 1, în ordinea în care sunt date.

Date de intrare

Fişierul de intrare treesmen.in conţine pe prima linie un numar natural N, ce reprezintă numărul de noduri ale 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 următoarea linie se află un număr natural M, ce reprezintă numărul de operaţii. Pe următoarele M linii se află operaţiile, sub forma descrisă în enunţ.

Date de ieşire

În fişierul de ieşire treesmen.out se vor afişa răspunsurile pentru operaţiile de tipul 1 în ordinea primită în fişierul de intrare.

Restricţii

  • 1 ≤ N, M ≤ 10^5
  • 1 ≤ p, r ≤ 10^3
  • x tot timpul va fi un strămoş al lui y
  • Dacă Antonio rezolvă această problemă de 100 puncte, Antonia va fi impresionată şi vor trăi fericiţi până la adânci bătrâneţi!

Exemplu

treesmen.intreesmen.out
10
1 1 1 2 2 4 7 8 7
9
0 1 5 3 2
0 2 5 2 3
1 1
1 5
0 4 9 1 3
1 7
0 4 10 2 1
1 8
1 10
3
12
4
7
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content