Phân Bố Kênh Sóng Trên Cây Mạng

Buổi 64 — Contest Chặng 7 Mathematics Trees
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Một mạng truyền thông gồm $N$ trạm phát (đánh số từ $1$ đến $N$) được kết nối với nhau thành một cây gồm $N-1$ tuyến cáp. Kỹ sư cần gán cho mỗi trạm một kênh tần số từ tập $K$ kênh hợp lệ ${1, 2, \dots, K}$. Để tránh nhiễu sóng chéo, bất kỳ hai trạm phân biệt nào có khoảng cách trên cây không vượt quá $2$ cạnh đều phải sử dụng hai kênh tần số khác nhau.

Hãy đếm số cách phân bố kênh tần số hợp lệ cho toàn bộ $N$ trạm, lấy phần dư khi chia cho $10^9 + 7$.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, K$ ($1 \le N \le 10^5$, $1 \le K \le 10^9$).
  • $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i, v_i$ ($1 \le u_i, v_i \le N$, $u_i \ne v_i$) mô tả một tuyến cáp của cây.
Dữ liệu ra

In ra một số nguyên duy nhất là số cách phân bố hợp lệ theo modulo $10^9 + 7$.

Ví dụ
Input Output
4 3
1 2
2 3
3 4
6
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved