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 ≤ N, M ≤ 300 000
• $1 ≤ valoare_i ≤ 2 \ 000 \ 000 \ 000$, pentru orice i, 1 ≤ i ≤ N.
• 1 ≤ x, y ≤ N Atenție! Nodul x este unul dintre nodurile de pe lanțul 1 – y!
• Pentru 40% din teste, N ≤ 1000 și M ≤ 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.