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
Fișierul de ieșire arbvalmax.out va conține, 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
• 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.
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.