arb3

Arb3

== include(page="template/taskheader" task_id="arb3") ==

Poveste şi cerinţă...

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$.
 
h2. 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ă)

h2. Date de intrare

Fişierul de intrare $arb3.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $arb3.out$ ...

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

h2. 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$.
 

h2. Exemplu
table(example). |_. arb3.in |_. arb3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 3
  1 1 3 3
  10 7 5 2 3
  4 2
  5 3
  3 1
| 12
  10
  4

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="arb3") ==