CSES - Datatähti 2020 loppu - Kierrokset
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Bittimaassa on $n$ kaupunkia ja niiden välillä $n-1$ tietä. Jokaisen kahden kaupungin välillä on jokin reitti.

Tehtäväsi on suunnitella turistikierros, joka alkaa kaupungista $x$, kulkee teitä pitkin ja päättyy kaupunkiin $y$. Kaksi kierrosta ovat erilaiset, jos on jokin kaupunki, jossa käyt vain toisessa kierroksista.

Montako erilaista turistikierrosta voit suunnitella?

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua $n$, $x$ ja $y$. Kaupungit on numeroitu $1,2,\dots,n$.

Seuraavat $n-1$ riviä kuvaavat tiet. Kullakin rivillä on kaksi kokonaislukua $a$ ja $b$: kaupunkien $a$ ja $b$ välillä on tie.

Tuloste

Tulosta yksi kokonaisluku: erilaisten turistikierrosten määrä. Koska vastaus voi olla suuri, tulosta se modulo $10^9+7$.

Esimerkki

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


Tuloste:
16

Osatehtävä 1 (22 pistettä)
  • $1 \leq n \leq 10$
Osatehtävä 2 (25 pistettä)
  • $1 \leq n \leq 2 \cdot 10^5$
  • kustakin kaupungista lähtee enintään kaksi tietä
Osatehtävä 3 (26 pistettä)
  • $1 \leq n \leq 2 \cdot 10^5$
  • $x = y$, eli kierros alkaa ja päättyy samassa kaupungissa
Osatehtävä 4 (27 pistettä)
  • $1 \leq n \leq 2 \cdot 10^5$