Fişierul intrare/ieşire:arb3.in, arb3.outSursăLot Botosani 2012 - Baraj 1 Seniori
AutorAndrei CiocanAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Arb3

Se dă un arbore cu n noduri numerotate de la 1 la n şi rădăcina nodul 1, în care fiecare nod are asociată o valoare distinctă. Pe acest arbore se fac un număr infinit de drumuri: se pleacă din nodul rădăcină şi la fiecare pas, pentru nodul curent se alege fiul cu valoarea cea mai mare până se ajunge la o frunză. Odată parcurs un nod, acestuia îi scade valoarea cu o unitate. Dacă la un moment dat sunt doi fii cu aceeaşi valoare, se alege cel care iniţial a avut valoarea mai mare. Mai mult, se garantează că înălţimea arborelui este mai mică sau egală cu 20.

Cerinţă

Să se răspundă la întrebări de forma (x,y) având următoarea semnificaţie: după câte astfel de drumuri nodul x va fi parcurs de exact y ori? (adică drumul la care nodul x a fost accesat a y-a oară)

Date de intrare

Fişierul de intrare arb3.in conţine pe prima linie două numere naturale n şi q despărţite printr-un spaţiu, ce reprezintă, în ordine, numărul de noduri al arborelui şi 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. Pe a treia linie se află n numere naturale despărţite prin câte un spaţiu reprezentând valorile celor n noduri în ordinea crescătoare a indicilor. Următoarele q linii conţin câte două numere naturale x şi y separate printr-un spaţiu: nodul de interes, respectiv numărul de accesări al acestuia.

Date de ieşire

Fişierul de ieşire arb3.out va conţine q linii reprezentând răspunsul fiecărei întrebări.

Restricţii

  • 2 ≤ n , q ≤ 100 000
  • Valorile din noduri sunt numere naturale mai mici sau egale cu 1 000 000 000.
  • Pentru fiecare întrebare răspunsul se reprezintă pe 32 de biţi cu semn.
  • Înălţimea arborelui este mai mică sau egală decât 20.

Exemplu

arb3.inarb3.out
5 3
1 1 3 3
10 7 5 2 3
4 2
5 3
3 1
12
10
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?