DRŽAVNO NATJECANJE 2013. – Drugi dan natjecanja / Srednja škola, I. podskupina (1. i 2. razred) - 2. zadatak

Mirko je osnovao Iskru, svjetski poznato poduzeće u kojem se trenutno nalazi N zaposlenika (uključujući i Mirka), označenih rednim brojevima od 1 do N (Mirko ima redni broj 1).

Iskra je vrlo strukturirana: svaki zaposlenik (osim Mirka) ima točno jednog izravno nadređenog zaposlenika, ali svaki zaposlenik može imati više različith zaposlenika koji su mu izravno podređeni.

Dakle, zaposlenici čine stablo na čijem se korijenu nalazi veliki šef Mirko.

Kako bi se zaposlenici bolje upoznali, Iskra organizira turnir u odbojci.

Za svakog od zaposlenih izračunali su sposobnost igranja odbojke: zaposlenik i ima sposobnost Si gdje je Si cijeli broj (može biti pozitivan, negativan ili nula).

Jedan tim se sastoji od jednog ili više zaposlenika.

U timu niti jedan član neće imati više od jednog izravno podređenog, a točno jedan član neće imati niti jednog izravno podređenog.

Drugim riječima, svaki tim možemo konstruirati tako da uzmemo jednog zaposlenika X1, pa dodamo njegovog izravno nadređenog X2, pa dodamo izravno nadređenog od X2 i tako dalje određen broj koraka.

Kažemo da tim je valjan ukoliko je suma sposobnosti svih članova tima točno jednaka zadanom broju M.

Dva tima smatramo različitima ako u jednom timu postoji zaposlenik koji se ne nalazi u drugom timu.

Napišite program koji na temelju hijerarhije poduzeća za zadani broj M pronalazi broj različitih valjanih timova koji se mogu sastaviti.

Ulazni podaci

U prvom retku ulaza nalaze se dva prirodna broja, N i M (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 1 000 000), broj zaposlenika u poduzeću i željena ukupna sposobnost članova svakog tima.

U drugom retku nalazi se N brojeva Si (-10 ≤ Si ≤ 10) koji označavaju sposobnosti svakog od zaposlenika – i-ti po redu broj u redu je sposobnog i-tog zaposlenika.

U sljedećih N-1 redaka nalaze se po dva broja, A, B (1 ≤ A < B ≤ N) koji definiraju odnose u poduzeću: zaposlenik s rednim brojem A je izravno nadređen zaposleniku s rednim brojem B.

Izlazni podaci

U prvi i jedini redak potrebno je ispisati broj različitih valjanih timova koji se mogu složiti.

Primjeri test podataka

Ulaz

5 4
4 -4 0 4 -4
1 2
2 3
3 4
4 5

Izlaz

4

Ulaz

5 3
1 2 2 0 0
1 2
1 3
2 4
3 5

Izlaz

4