Đua Xe Rừng

Đ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

Có $N$ đỉnh và $M$ cạnh tạo thành một rừng (đồ thị không có chu trình), với $K = N - M$ cây. Mỗi cạnh có độ dài dương và mỗi đỉnh có ít nhất một cạnh nối.

Bessie muốn xây một vòng đua bằng cách:

Chọn một đường đi (giữa hai đỉnh phân biệt) trong mỗi cây.
Nối $K$ cây theo một thứ tự vòng tròn bằng $K$ cạnh mới, mỗi cạnh có độ dài $X$ .

Tổng độ dài vòng đua = tổng độ dài $K$ đường đi + $K \cdot X$ . Hai vòng đua khác nhau nếu có hai đỉnh kề nhau ở vòng đua này nhưng không kề nhau ở vòng đua kia.

Hãy tính tổng độ dài của tất cả các vòng đua có tổng độ dài $\geq Y$ , lấy kết quả modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu: bốn số nguyên $N$ , $M$ , $X$ , $Y$ ( $1 \leq N \leq 1500$ , $1 \leq M \leq N - 1$ , $0 \leq X, Y \leq 2500$ )
$M$ dòng tiếp theo: mỗi dòng gồm $A_{i}$ , $B_{i}$ , $D_{i}$ (cạnh nối đỉnh $A_{i}$ và $B_{i}$ có độ dài $D_{i} \geq 1$ )

Dữ liệu ra

Tổng độ dài tất cả các vòng đua hợp lệ, modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq N \leq 1500$ , $1 \leq M \leq N - 1$
$0 \leq X, Y \leq 2500$
Đồ thị là rừng, mỗi đỉnh có ít nhất một cạnh nối

Ví dụ

Input	Output	Giải thích
5 3 1 12 1 2 3 2 3 4 4 5 6	54	$K = 2$ cây: cây ${1, 2, 3}$ (đường đi dài 3, 4, hoặc 7) và cây ${4, 5}$ (đường đi dài 6). Cạnh nối dài $X = 1$ , tổng cạnh nối $2$ . Các vòng đua dài $\geq 12$ : $4 + 6 + 2 = 12$ (×2), $7 + 6 + 2 = 15$ (×2). Tổng $= 12 + 12 + 15 + 15 = 54$ .
4 2 2 8 1 2 3 3 4 4	22	$K = 2$ cây: ${1, 2}$ (đường đi dài 3) và ${3, 4}$ (đường đi dài 4). Cạnh nối dài $X = 2$ , tổng cạnh nối $= 4$ . Vòng đua dài $3 + 4 + 4 = 11 \geq 8$ . Có 2 vòng đua khác nhau (hướng đi khác nhau), tổng $= 11 \times 2 = 22$ .

Bình luận

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