sap

Se dă un arbore cu $N$ noduri numerotate de la $1$ la $N$, cu rădăcina în nodul $1$, și un vector $V$, unde $V_i$ reprezintă valoarea nodului $i$.

Un șir de lungime $N$ se numește permutare de ordin $N$ dacă acesta conține toate numerele de la $1$ la $N$, în orice ordine. De exemplu, șirurile $[1, 2, 3]$, $[2, 1, 3]$ și $[3, 2, 1]$ sunt permutări de ordin $3$, dar șirurile $[1, 4, 3]$ și $[1, 2, 2]$ nu sunt.

Cerință

Se dau $Q$ întrebări de tipul: Dacă am forma un șir cu toate valorile nodurilor din subarborele nodului $X$, este acest șir o permutare de ordin $K$, unde $K$ reprezintă numărul de noduri din subarborele nodului $X$?

Să se raspundă la aceste întrebări.

Date de intrare

Pe prima linie se găsește numărul natural $N$. Pe următoarea linie, regăsim $N$ numere naturale, separate printr-un spațiu, reprezentând vectorul $V$. Pe următoarea linie găsim $N - 1$ perechi de numere naturale $(a, b)$, separate printr-un spațiu, cu semnificația că există muchie între nodurile $a$ și $b$. Pe următoarea linie, găsim numărul natural $Q$. Pe următoarele $Q$ linii, regăsim nodurile $X$, cu semnificația de mai sus.

Date de ieșire

Pe următoarele $Q$ linii se vor regăsi mesajul DA sau NU, reprezentând răspunsurile la cele $Q$ întrebări.

Restricții și precizări

• $1 \leq N, Q \leq 500 \ 000$
• $1 \leq a, b \leq N$
• $1 \leq V_i \leq N$, pentru $1 \leq i \leq N$
• $1 \leq X \leq N$

  #	Punctaj	Restricții
  0	0	Exemplul
  1	21	$N, Q \leq 100$
  2	23	Arborele este un lanț
  3	27	$N, Q \leq 100 \ 000$
  4	29	Fără alte restricții suplimentare

Observație

Datorită datelor de intrare foarte mari, se vor folosi instrucțiunile următoare la începutul funcției main() în programul C++:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Exemplu

stdin

8
6 5 4 7 8 2 1 3
1 2
1 3
2 4
2 5
3 6
6 7
6 8
6
1
2
6
3
5
7

stdout

DA
NU
DA
DA
NU
DA

Explicație

Pentru prima întrebare, putem obține șirul $[1, 2, 3, 4, 5, 6, 7, 8]$, care este o permutare de ordin $8$.

Pentru a doua întrebare, putem obține șirul $[5, 7, 8]$, care nu este o permutare de ordin $3$, deoarece nu conține toate numerele de la $1$ la $3$.

Pentru ultima întrebare, obținem șirul $[1]$, care este o permutare de ordin $1$.