Fişierul intrare/ieşire:arbvalmax.in, arbvalmax.outSursăONI 2015 Clasele 11-12
AutorRazvan SalajanAdăugată deassa98Andrei Stanciu assa98
Timp execuţie pe test0.8 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inarbvalmax.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?