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

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.

Poveste şi cerinţă...

h2. Date de intrare

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.
 

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

h2. Date de ieşire

 
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.
 

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

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 |

| 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

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

|
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") ==