Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | impiedicat.in, impiedicat.out | Sursă | ONI 2023, Baraj Seniori, ziua 2 |
| Autor | Adrian Budau, Costin Oncescu | Adăugată de |  Voicu Mihai-Valeriu •cadmium_ |
| Timp execuţie pe test | 1 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Impiedicat
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 pi, intersecţia părinte a intersecţiei i şi di, dimensiunea unui monument din intersecţie.
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.
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 d1, d2,..., dn. Pe a treia linie, se află N − 1 valori reprezentând şirul p2, p3,..., pn. Pe următoarele Q linii se afla câte două numere xi, yi ce descriu a i-a întrebare.
Date de ieşire
Î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.
Restricţii
- 1 ≤ N ≤ 200 000
- 1 ≤ Q ≤ 200 000
- 1 ≤ pi ≤ N
- 1 ≤ di ≤ N
- Nodul 1 nu are parinte.
Subtask-uri
| # | 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 |
Exemplu
| 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 |
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 roşu s-au marcat monumentele de care Gimi se loveşte în timpul zborului.
