Gánh Xiếc

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông dân John đang chuẩn bị biểu diễn gánh xiếc với $N$ con bò, được đánh số từ $1$ đến $N$ . Sân khấu gánh xiếc được biểu diễn bởi một cây gồm $N$ đỉnh được đánh số từ $1$ đến $N$ .

Một trạng thái khởi đầu cho $K$ con bò ( $1 \leq K \leq N$ ) là cách gán $K$ con bò phân biệt (được đánh số từ $1$ đến $K$ ) vào $K$ đỉnh phân biệt của cây. Một bước di chuyển là: chọn một con bò và di chuyển nó đến một đỉnh kề chưa bị chiếm. Hai trạng thái được gọi là tương đương nếu có thể đến được từ trạng thái này sang trạng thái kia bằng một số hữu hạn bước di chuyển.

Với mỗi $K$ từ $1$ đến $N$ , hãy đếm số lớp tương đương của các trạng thái khởi đầu cho $K$ con bò. In kết quả modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng $1$ : Số nguyên $N$ — số đỉnh của cây.
$N - 1$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $u$ và $v$ ( $1 \leq u, v \leq N$ ) mô tả một cạnh của cây.

Dữ liệu ra

In $N$ dòng. Dòng $K$ là số lớp tương đương cho $K$ con bò, modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq N \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
5 1 2 2 3 3 4 3 5	1 1 3 24 120	Cây có $5$ đỉnh: đường đi $1$ - $2$ - $3$ và các cạnh $3$ - $4$ , $3$ - $5$ . Với $K = 1$ : 1 lớp. Với $K = 3$ : 3 lớp tương đương. Với $K = 5$ : $5! = 120$ lớp (mỗi hoán vị là một lớp riêng).
8 1 3 2 3 3 4 4 5 5 6 6 7 6 8	1 1 1 6 30 180 5040 40320	Cây có $8$ đỉnh: đỉnh $3$ nối với $1$ , $2$ , $4$ ; đỉnh $6$ nối với $5$ , $7$ , $8$ . Với $K \leq 3$ : chỉ có $1$ lớp tương đương vì các con bò có thể sắp xếp tự do. Với $K = 7$ : $7!$ lớp.

Ghi chú

Hai con bò được coi là phân biệt (có đánh số), nên việc hoán đổi vị trí của hai con bò tạo ra trạng thái khác.
Khi $K = N$ : tất cả $N!$ trạng thái đều thuộc các lớp tương đương khác nhau (mỗi trạng thái là một lớp riêng).
Khi $K$ nhỏ (nhiều đỉnh trống), các con bò có thể di chuyển tự do và tất cả trạng thái về cơ bản là tương đương.

Bình luận

Không có bình luận tại thời điểm này.