Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | arbore3.in, arbore3.out | Sursă | Algoritmiada 2010, Runda 3 |
| Autor | Cosmin Silvestru Negruseri | Adăugată de |  Gheorghe Cosmin •gcosmin |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 128000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arbore3
 In momentul in care trimiti o sursa, vei putea vedea scorul obtinut pe o parte din testele folosite la evaluare in monitor. |
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.
Date de intrare
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.
Date de ieşire
Î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.
Restricţii
- 1 ≤ N ≤ 1 000 000
- Numerele S si Vi fi 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
Exemplu
| arbore3.in | arbore3.out |
|---|---|
| 8 5 0 1 1 3 2 1 2 5 1 7 5 -4 6 7 6 2 | 3 |
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.
