Fişierul intrare/ieşire:arbore3.in, arbore3.outSursăAlgoritmiada 2010, Runda 3
AutorCosmin Silvestru NegruseriAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test1.5 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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 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

Exemplu

arbore3.inarbore3.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content