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

Poveste şi cerinţă...

 
Se da un arbore cu $N$ noduri si radacina in nodul $1$, in care fiecare nod $i$ are asociata o valoare intreaga $Vi$. Se defineste un drum _in jos_ in arbore ca fiind orice lant elementar ce uneste un nod $A$ cu alt nod $B$ din subarborele lui $A$. Se cere sa se determine pentru o suma data $S$ cate drumuri _in jos_ exista, astfel incat suma valorilor nodurilor de pe drum sa fie egala cu $S$.

h2. Date de intrare

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

Fişierul de intrare $arbore3.in$ va contine pe prima linie numerele $N$ si $S$. Urmatoarele $N$ linii vor contine fiecare cate doua numere: linia $i+1$ va contine $Ti$ si $Vi$ reprezentand tatal nodului $i$ in arbore si respectiv, valoarea asociata nodului $i$. Pentru comoditate se considera ca tatal nodului $1$ (radacina) este $0$.

h2. Date de ieşire

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

În fişierul de ieşire $arbore3.out$ veti afisa o singura valoare reprezentand numarul de dumuri _in jos_ cu suma valorilor nodurilor egala cu $S$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1 000 000$
* Numerele $S$ si $Vi$ fi numere intregi (cu semn) pe $32$ de biti
* Nodul $1$ (radacina) este singurul care apare cu tatal $0$

h2. Exemplu