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
table(example). |_. arbore3.in |_. arbore3.out |

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

| 8 5
0 1
1 3
2 1
2 5
1 7
5 -4
6 7
6 2
| 3

|
h3. Explicaţie

...

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