Candale Silviu (silviu) 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ța
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 și precizări
1 ≤ N, M ≤ 300 0001 ≤ valoare[i] ≤ 2 000 000 000, pentru oricei,1 ≤ i ≤ N.1 ≤ x, y ≤ NAtenție! Nodulxeste unul dintre nodurile de pe lanțul1 – 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ție
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.