Code Submission Evaluation System Login

IOI-leiri 2016

Polut


Task | Statistics


CSES - PolutCSES - Polut

Time limit:1.00 s Memory limit:128 MB

Annettuna on puu, jossa on $n$ solmua. Tehtäväsi on laskea, monessako puun polussa on tasan $k$ kaarta.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $k$: solmujen määrä ja haluttu polun pituus. Solmut on numeroitu $1,2,\ldots,n$.

Tämän jälkeen syötteessä on $n-1$ riviä, jotka kuvaavat verkon kaaret. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: kaari kulkee solmujen $a$ ja $b$ välillä.

Tuloste

Tulosta, montako $k$-pituista polkua puussa on.

Rajat
Esimerkki

Syöte:
5 2
1 2
2 3
3 4
3 5


Tuloste:
4