Se dă un arbore cu N noduri numerotate de la 1 la N, rădăcina fiind nodul cu numărul 1.
Fiecare nod i (1<=i<=N) are asociată o valoare Ci.
Trebuie să răspundem la întrebări de tipul: „Care este suma valorilor asociate nodurilor din subarborele cu rădăcina în nodul i aflate la distanţă cel mult egală cu j faţă de nodul i?”.
Distanţa de la un nod x la un nod y este egală cu numărul de muchii de pe drumul de la x la y.
Cerinţă
Să se scrie un program care să răspundă la M întrebări de tipul specificat.
Date de intrare
Fişierul de intrare arb.in conţine pe prima linie numărul natural N. Pe a doua linie se află N numere reprezentând costurile asociate celor N noduri. Pe cea de a treia linie se află N-1 numere, cel de-al i-lea număr reprezentând părintele nodului cu numărul i+1. Pe a patra linie se află numărul natural M. Pe următoarele M linii se află câte două numere naturale i j reprezentând o întrebare de tipul specificat în enunţ (i este rădăcina subarborelui, iar j este distanţa maximă). Valorile aflate pe aceeaşi linie sunt separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire arb.out va conţine M linii. Linia i conţine un singur număr natural reprezentând răspunsul la cea de a i-a întrebare din fişierul de intrare.
Restricţii
1 ≤ N ≤ 250 000
1 ≤ M ≤ 500 000
0 ≤ Ci ≤ 5000, 1≤i≤N