Fişierul intrare/ieşire:colorare3.in, colorare3.outSursăStelele Informaticii 2010
AutorBogdan-Cristian TataroiuAdăugată destef2nStefan Istrate stef2n
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.incolorare3.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content