Phân Bố Kênh Sóng Trên Cây Mạng
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề 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.
Community Discussion