== include(page="template/taskheader" task_id="arb") ==

Poveste şi cerinţă...

Se da un arbore cu $N$ noduri numerotate de la $1$ la {$N$}, radacina fiind nodul cu numarul {$1$}.
Fiecare nod {$i$}, {$1 ≤ i ≤ N$} are asociata o valoare {$C{~i~}$}.
Trebuie sa raspundem la intrebari de tipul:
 
* Care este suma valorilor asociate nodurilor din subarborele cu radacina in nodul {$i$} aflate la distanta cel mult egala cu {$j$} fata de nodul {$i$}?
Distanta de la un nod {$x$} la un nod {$y$} este egala cu numarul de muchii de pe drumul de la {$x$} la {$y$}.
 
h2. Cerinta
 
Sa se scrie un program care sa raspunda la $M$ intrebari de tipul specificat.

h2. Date de intrare

Fişierul de intrare $arb.in$ ...

Fisierul de intrare $arb.in$ contine pe prima linie numarul natural {$N$}. Pe a doua linie se afla $N$ numere reprezentand costurile asociate celor $N$ noduri. Pe cea de a treia linie se afla {$N-1$} numere, cel de-al {$i$}-lea numar reprezentand parintele nodului cu numarul {$i+1$}. Pe a patra linie se afla numarul natural {$M$}. Pe urmatoarele $M$ linii se afla cate doua numere naturale $i$ $j$ reprezentand o intrebare de tipul specificat in enunt ({$i$} este radacina subarborelui, iar $j$ este distanta maxima). Valorile aflate pe aceeasi linie sunt separate prin cate un spatiu.

h2. Date de ieşire

h2. Date de iesire

În fişierul de ieşire $arb.out$ ...

Fisierul de iesire $arb.out$ va contine $M$ linii. Linia $i$ contine un singur numar natural reprezentand raspunsul la cea de a {$i$}-a intrebare din fisierul de intrare.

h2. Restricţii

* $... ≤ ... ≤ ...$

* {$1 ≤ N ≤ 250.000$}
* {$1 ≤ M ≤ 500.000$}
* {$0 ≤ C{~i~} ≤ 5.000, 1 ≤ i ≤ N$}

h2. Exemplu
table(example). |_. arb.in |_. arb.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|7
1 2 2 1 3 4 5
1 1 1 3 3 6
3
3 1
3 2
1 0
|9
14
1

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="arb") ==