| Fişierul intrare/ieşire: | colorare3.in, colorare3.out | Sursă | Stelele Informaticii 2010 |
| Autor | Bogdan-Cristian Tataroiu | Adăugată de |  Stefan Istrate •stef2n |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Colorare3
În Oraşul Simplu au avut loc de curând alegeri pentru funcţia de primar. Cel care a fost ales a câştigat mai ales datorită proiectului său de restaurare a faţadelor tuturor clădirilor, iar acum trebuie să-l pună în practică. Oraşul Simplu constă din N obiective între care există străzi, în aşa fel încât pentru oricare 2 astfel de obiective există un singur drum de a ajunge de la unul la celălalt mergând pe străzi. Planul primarului constă în colorarea tuturor caselor astfel încât casele de pe aceeaşi stradă să aibă aceeaşi culoare, iar pentru oricare 2 străzi care se întâlnesc în acelaşi obiectiv, culorile să fie diferite. Ştiind ca primarul are la dispoziţie K culori, ar vrea să afle câte posibilităţi sunt de a-şi realiza planul de colorare.
Date de intrare
Fişierul de intrare colorare3.in conţine pe prima linie numerele N şi K. Urmează N - 1 linii, fiecare conţinând câte 2 numere a şi b semnificând faptul că există o stradă între obiectivele a şi b.
Date de ieşire
În fişierul de ieşire colorare3.out se va scrie numărul de posibilităţi de colorare modulo 1 000 000 007.
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ K ≤ 1 000 000 000
- Obiectivele sunt numerotate de la 1 la N.
Exemplu
| colorare3.in | colorare3.out |
|---|---|
| 5 3 1 2 1 3 1 4 3 5 | 12 |
Explicaţie
Se observă că după ce alegem culorile pentru străzile (1,2), (1,3), (1,4) (având 6 posibilităţi), strada (3,5) poate fi colorată în 2 moduri: cu aceeaşi culoare ca (1,2) sau (1,4). Cu mai puţin de 3 culori nu se poate realiza planul. Aşadar, 6 * 2 = 12.
