Fişierul intrare/ieşire:arb.in, arb.outSursăLot Iasi 2008, Baraj 6
AutorAdrian DiaconuAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Arb

Se da un arbore cu N noduri numerotate de la 1 la N, radacina fiind nodul cu numarul 1.
Fiecare nod i, 1 ≤ i ≤ N are asociata o valoare Ci.
Trebuie sa raspundem la intrebari de tipul:

  • Care este suma valorilor asociate nodurilor din subarborele cu radacina in nodul i aflate la distanta cel mult egala cu j fata de nodul i?

Distanta de la un nod x la un nod y este egala cu numarul de muchii de pe drumul de la x la y.

Cerinta

Sa se scrie un program care sa raspunda la M intrebari de tipul specificat.

Date de intrare

Fisierul de intrare arb.in contine pe prima linie numarul natural N. Pe a doua linie se afla N numere reprezentand costurile asociate celor N noduri. Pe cea de a treia linie se afla N-1 numere, cel de-al i-lea numar reprezentand parintele nodului cu numarul i+1. Pe a patra linie se afla numarul natural M. Pe urmatoarele M linii se afla cate doua numere naturale i j reprezentand o intrebare de tipul specificat in enunt (i este radacina subarborelui, iar j este distanta maxima). Valorile aflate pe aceeasi linie sunt separate prin cate un spatiu.

Date de iesire

Fisierul de iesire arb.out va contine M linii. Linia i contine un singur numar natural reprezentand raspunsul la cea de a i-a intrebare din fisierul de intrare.

Restricţii

  • 1 ≤ N ≤ 250.000
  • 1 ≤ M ≤ 500.000
  • 0 ≤ Ci ≤ 5.000, 1 ≤ i ≤ N

Exemplu

arb.inarb.out
7
1 2 2 1 3 4 5
1 1 1 3 3 6
3
3 1
3 2
1 0
9
14
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content