Sinh Cây Ngẫu Nhiên

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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

Bessie tạo cây ngẫu nhiên có nhãn gồm $N$ đỉnh qua hai bước:

Bước 1: Bắt đầu với các đỉnh $1$ đến $N$ . Với mỗi $i$ từ $2$ đến $N$ , nối đỉnh $i$ với một đỉnh ngẫu nhiên đều trong ${1, 2, \dots, i - 1}$ .

Bước 2: Chọn một hoán vị ngẫu nhiên đều $p_{1}, p_{2}, \dots, p_{N}$ của ${1, \dots, N}$ . Đổi nhãn mỗi đỉnh $v$ thành $p_{v}$ .

Cho tập cạnh cuối cùng, tính xác suất mà quá trình trên sinh ra tập cạnh này. Kết quả modulo $10^{9} + 7$ .

Dòng 1: Số nguyên $T$ — số bộ test ( $1 \leq T \leq 10$ )
Với mỗi bộ test:
- Dòng 1: Số nguyên $N$ ( $2 \leq N \leq 2 \times 10^{5}$ )
- $N - 1$ dòng tiếp theo: Hai số nguyên $u, v$ mô tả cạnh

Tổng $N$ trên tất cả bộ test không vượt quá $5 \times 10^{5}$ .

Với mỗi bộ test, in ra xác suất modulo $10^{9} + 7$ .

Input	Output	Giải thích
4 2 2 1 3 1 2 2 3 4 1 2 2 3 2 4 4 1 2 2 3 3 4	1 333333336 83333334 55555556	$N = 2$ : xác suất $1$ . $N = 3$ , đường thẳng: xác suất $1 / 3$ . $N = 4$ , sao: $1 / 12$ . $N = 4$ , đường thẳng: $1 / 18$ .

Bình luận

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