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

== include(page="template/detailed-feedback" task_id="arbore3") ==
 

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

h2. Restricţii
* $1 ≤ N ≤ 1 000 000$

* Numerele $S$ si $Vi$ fi numere intregi *cu semn* pe $32$ de biti

* Numerele $S$ si $Vi$ sunt numere intregi *cu semn* pe $32$ de biti

* Pentru orice drum _in jos_, suma valorilor nodurilor de pe drum se va incadra intr-un intreg *cu semn* pe $32$ de biti
* Nodul $1$ (radacina) este singurul care apare cu tatal $0$

4540