== include(page="template/taskheader" task_id="impiedicat") ==
Poveste şi cerinţă...
!{float: right; width: 350px; margin: 10px; }problema/impiedicat?stupid-gugustiuc.png!
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.
h2. Cerinţă
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ă.
Gimi vrea să ştie, pentru fiecare zbor din cele $Q$, de câte monumente se va lovi.
h2. Date de intrare
Fişierul de intrare $impiedicat.in$ ...
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
În fişierul de ieşire $impiedicat.out$ ...
Î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 ≤ N ≤ 200 000$
* $1 ≤ Q ≤ 200 000$
* $1 ≤ p{~i~} ≤ N$
* $1 ≤ d{~i~} ≤ N$
* Nodul $1$ nu are parinte.
h2. Subtask-uri
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$ |
| $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:
%{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 %{color:red}roşu% s-au marcat monumentele de care Gimi se loveşte în timpul zborului.
== include(page="template/taskfooter" task_id="impiedicat") ==
