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- , pentru orice
i,1 ≤ i ≤ N. 1 ≤ x, y ≤ NAtenție! Nodul x este unul dintre nodurile de pe lanțul 1 – y!- Pentru
40%din teste,N ≤ 1000șiM ≤ 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.