| Fişierul intrare/ieşire: | arb.in, arb.out | Sursă | Lot Iasi 2008, Baraj 6 |
| Autor | Adrian Diaconu | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | arb.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 |
