Arbvalmax

Se dă un arbore cu $N$ noduri numerotate de la $1$ la $N$ cu rădăcina în nodul $1$. Fiecare nod din arborele dat are o valoare întreagă atașată. Se dau $M$ întrebări de forma $(x, y)$, unde $x$ este un strămoș al nodului $y$: dacă s-ar elimina toate nodurile de pe lanțul care unește $x$ cu $y$ (inclusiv nodurile $x$ și $y$), care ar fi valoarea maximă din nodurile neeliminate?

Cerință

Cunoscând numărul de noduri $N$, configurația arborelui, valorile atașate celor $N$ noduri, și cele $M$ întrebări, să se răspundă la fiecare întrebare dată.

Date de intrare

Fișierul de intrare arbvalmax.in conține pe prima linie două numere naturale $N$ și $M$ separate printr-un spațiu, reprezentând numărul de noduri ale arborelui, respectiv numărul de întrebări. A doua linie a fișierului conține $N-1$ numere naturale despărțite prin câte un spațiu. Al $i$-lea număr de pe această linie reprezintă părintele nodului cu indicele $i+1$. A treia linie a fișierului conține $N$ numere întregi separate prin câte un spaţiu. Al $i$-lea număr de pe această linie reprezintă valoarea atașată nodului cu indicele $i$. Pe următoarele $M$ linii se află câte două numere $x$, $y$ separate prin câte un spaţiu, reprezentând câte o întrebare de forma descrisă în enunț.

Date de ieșire

În fișierul de ieșire arbvalmax.out se vor afișa, câte unul pe linie, $M$ numere reprezentând răspunsurile pentru cele $M$ întrebări, în ordinea primită în fișierul de intrare.

Restricții și precizări

• $ 1 \leq N, M \leq 300 000$
• $ 1 \leq valoare_i \leq 2 000 000 000$, pentru orice $i$, $1 \leq i \leq N$.
• $ 1 \leq x, y \leq N$. Atenție! Nodul $x$ este unul dintre nodurile de pe lanțul $1 – y$ !
• Pentru 40% din teste, $N \leq 1000$ și $M \leq 10 000$.
• Adâncimea maximă a arborelui nu va depăși valoarea de $100 000$.

Exemplu

arbvalmax.in

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

arbvalmax.out

6
10
7 

Explicaţii

Arborele conține următoarele muchii: $1-2$, $2-3$, $2-4$, $1-5$, $5-6$, $4-7$, $5-8$.

Pentru prima întrebare, dacă s-ar elimina nodurile de pe lanțul $1-7$ ($1$, $2$, $4$, $7$), nodurile rămase ar fi: $3$, $5$, $6$, $8$ și ar avea valorile: $6$, $3$, $5$, $4$. Dintre acestea valoarea maximă este $6$.