impiedicat

Impiedicat

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

!{float: right; width: 350px; margin: 10px; }problema/impiedicat?stupid-gugustiuc.png!

h2. Cerinta

Gimi guguştiucul a intrat din nou în belele, el vizitează un oraş, sub formă de arbore cu $N$ intersecţii, conectate între ele prin $N − 1$ străzi bidirecţionale, înrădăcinat în intersecţia cu indicele $1$. Intersecţiile oraşului sunt numerotate de la $1$ la $N$, iar pentru fiecare intersecţie $i$ se cunosc $p{~i~}$, intersecţia părinte a intersecţiei $i$ şi $d{~i~}$, dimensiunea unui monument din intersecţie.

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.

h2. Cerinţă

Gimi vrea sa stie pentru fiecare zbor din cele $Q$ de cate monumente se va lovi.

Pe parcurs ce Gimi vizitează oraşul, acesta va face $Q$ zboruri plecând de la o intersecţie $x$, către o intersecţie $y$, vizitând toate intersecţiile de pe lanţul de la $x$ la $y$ în ordine. Cum guguştiucul nostru este foarte împiedicat, acesta se va lovi de fiecare monument mai mare sau egal decât toate monumentele din intersecţiile vizitate până atunci de pe lanţ. Astfel, guguştiucul se va lovi inclusiv de monumentul din intersecţia $x$ din care pleacă.

h2. Date de intrare

Gimi vrea să ştie, pentru fiecare zbor din cele $Q$, de câte monumente se va lovi.

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 intrare
Pe prima linie a fişierului de intrare $impiedicat.in$ se află două numere $N$ şi $Q$, reprezentând numărul de intersecţii, respectiv numărul de zboruri pe care Gimi le va efectua. Pe a doua linie se află N numere reprezentând şirul $d{~1~}, d{~2~},..., d{~n~}$. Pe a treia linie, se află $N − 1$ valori reprezentând şirul $p{~2~}, p{~3~},..., p{~n~}$. Pe următoarele $Q$ linii se afla câte două numere $x{~i~}, y{~i~}$ ce descriu a $i$-a întrebare.

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$ se vor afla $Q$ numere, fiecare pe câte o linie. Al $i$-lea număr reprezintă răspunsul la cea de-a $i$-a întrebare.

h2. Restricţii

* $1 ≤ d{~i~} ≤ N$
* Nodul $1$ nu are parinte.

h2. Subtaskuri

h2. Subtask-uri

table(restrictii). |_. # |_. Punctaj |_. Restricţii |

table(subtasks). |_. # |_. 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$   |

| $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 |

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*$

%{color:red}$1$% → %{color:red}$1$% → %{color:red}$2$% → %{color:red}$3$% → $1$
%{color:red}$1$% → %{color:red}$3$% → $2$ → $1$ → $1$
%{color:red}$1$% → %{color:red}$1$% → %{color:red}$2$% → %{color:red}$3$% → $2$
%{color:red}$2$% → %{color:red}$3$% → $2$ → $1$ → $1$
%{color:red}$1$% → %{color:red}$1$% → %{color:red}$2$% → %{color:red}$3$%
%{color:red}$3$% → $2$ → $1$ → $1$
%{color:red}$1$% → %{color:red}$2$% → %{color:red}$3$%
%{color:red}$3$% → $2$ → $1$
%{color:red}$1$% → %{color:red}$1$% → %{color:red}$2$% → %{color:red}$3$% → %{color:red}$4$%

Cu *bold* s-au marcat monumentele de care Gimi se loveşte în timpul zborului.

Cu %{color:red}roşu% s-au marcat monumentele de care Gimi se loveşte în timpul zborului.

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