== include(page="template/taskheader" task_id="treesmen") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $treesmen.in$ ...
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ţ.
h2. Date de ieşire
În fişierul de ieşire $treesmen.out$ ...
Î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.
h2. 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!$
h2. Exemplu
table(example). |_. treesmen.in |_. treesmen.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="treesmen") ==
