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

Poveste şi cerinţă...

Gimi gugustiucul a intrat din nou in belele, el viziteaza un oras, sub forma de arbore cu $N$ intersectii, conectate intre ele prin $N − 1$ strazi bidirectionale inradacinat in intersectia cu indicele $1$. Intersectiile orasului sunt numerotate de la $1$ la $N$, iar pentru fiecare intersectie i se cunosc p{~i~}, intersectia parinte a intersectiei $i$ si $d{~i~}$, dimensiunea unui monument din intersectie
 
h2. Cerinta
 
Pe parcurs ce Gimi viziteaza orasul, acesta va face $Q$ zboruri plecand de la o intersectie $x$, catre o intersectie $y$, vizitand toate intersectiile de pe lantul de la $x$ la $y$ in ordine. Cum gugustiucul nostru este foarte impiedicat acesta se va lovi de fiecare monument mai mare sau egal decat toate monumentele din intersectiile vizitate pana atunci de pe lant. Astfel, gugustiucul se va lovi inclusiv de monumentul din intersectia $x$ din care pleaca.
 
Gimi vrea sa stie pentru fiecare zbor din cele $Q$ de cate monumente se va lovi.

h2. Date de intrare

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

Pe prima linie a fisierului de intrare $impiedicat.in$ se afla doua numere $N$ si $Q$, reprezentand numarul de intersectii, respectiv numarul de zboruri pe care Gimi le va efectua. Pe a doua linie se afla N numere reprezentand sirul $d{~1~}, d{~2~},..., d{~n~}$. Pe a treia linie, se afla $N − 1$ valori reprezentand sirul $p{~2~}, p{~3~},..., p{~n~}$. Pe urmatoarele $Q$ linii se afla cate doua numere $x{~i~}, y{~i~}$ ce descriu a $i$-a intrebare.
 

h2. Date de ieşire

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

 
In fisierul de iesire $impiedicat.out$ se vor afla $Q$ numere, fiecare pe cate o linie. Al $i$-lea numar reprezinta raspunsul la cea de-a $i$-a intrebare.
 

h2. Restricţii

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

* $1 ≤ N ≤ 200 000$
* $1 ≤ Q ≤ 200 000$
* $1 ≤ p{~i~} ≤ N$
* $1 ≤ d{~i~} ≤ N$
* Nodul $1$ nu are parinte.
 
h2. Subtaskuri
 
table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $11$ | $N ≤ 2 000$ şi $Q ≤ 2 000$  |
| $2$ | $8$ | Arborele este un lanţ |
| $3$ | $9$ | Pentru fiecare interogare, $y$ este un strămoş al lui $x$ |
| $4$ | $28$ | Pentru fiecare interogare, $x$ este un strămoş al lui $y$   |
| $5$ | $21$ | $N ≤ 50 000$, $Q ≤ 50 000$ |
| $6$ | $23$ | Fără restricţii suplimentare |
 

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

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

| 8 9
3 2 4 1 3 1 2 1
1 1 2 2 4 5 1
6 8
8 6
6 7
7 6
6 1
1 6
4 5
5 4
6 3
| 4
2
4
2
4
1
3
1
5

|
h3. Explicaţie

...

Dimensiunile monumentelor vizitate pentru fiecare zbor sunt:
 
$*1* → *1* → *2* → *3* → 1$
$*1* → *3* → 2 → 1 → 1$
$*1* → *1* → *2* → *3* → 2$
$*2* → *3* → 2 → 1 → 1$
$*1* → *1* → *2* → *3*$
$*3* → 2 → 1 → 1$
$*1* → *2* → *3*$
$*3* → 2 → 1$
$*1* → *1* → *2* → *3* → *4*$
 
Cu *bold* s-au marcat monumentele de care Gimi se loveşte în timpul zborului.

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