arbore3

Arbore3

== include(page="template/taskheader" 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$
h2. Exemplu

0 1
1 3
2 1

2 2

2 5

1 7
5 -4

6 5

6 7

6 2

| 4

| 3

|
h3. Explicaţie

Cele $4$ lanturi sunt $(1, 2, 3)$, $(3, 2)$, $(5, 6, 8)$ si $(7)$.

Cele $3$ lanturi sunt $(1, 2, 3)$, $(4)$, $(5, 6, 8)$. **Observati** ca desi lantul $(8, 6, 7)$ are suma $5$ el nu este numarat pentru ca nu este un lant _in jos_.

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

4540