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 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 pi, intersectia parinte a intersectiei i si di, dimensiunea unui monument din intersectie
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.
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 d1, d2,..., dn. Pe a treia linie, se afla N − 1 valori reprezentand sirul p2, p3,..., pn. Pe urmatoarele Q linii se afla cate doua numere xi, yi ce descriu a i-a intrebare.
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.
Restricţii
- 1 ≤ N ≤ 200 000
- 1 ≤ Q ≤ 200 000
- 1 ≤ pi ≤ N
- 1 ≤ di ≤ N
- Nodul 1 nu are parinte.
Subtaskuri
| # | 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 bold s-au marcat monumentele de care Gimi se loveşte în timpul zborului.
