CSES - Polut II
  • 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 vähintään k_1 ja enintään k_2 kaarta.

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua n, k_1 ja k_2: solmujen määrä ja pienin sallittu polun pituus ja suurin sallittu 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 halutun pituista polkua puussa on.

Rajat

  • 1 \le k_1 \le k_2 < n \le 10^5

Esimerkki

Syöte:

5 2 3
1 2
2 3
3 4
3 5

Tuloste:

6