| Fişierul intrare/ieşire: | arbvalmax.in, arbvalmax.out | Sursă | ONI 2015 Clasele 11-12 |
| Autor | Razvan Salajan | Adăugată de |  Andrei Stanciu •assa98 |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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?
Cerinta
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
- 1 ≤ N, M ≤ 300 000
- 1 ≤ valoarei ≤ 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 | arbvalmax.out |
|---|---|
| 8 3 1 2 2 1 5 4 5 7 10 6 1 3 5 2 4 1 7 5 6 2 3 | 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.
