Xóa cạnh
Đề bài
Mô tả
Cho một cây gồm đỉnh và cạnh có trọng số. Các cạnh được đánh số từ đến , cạnh thứ nối cặp đỉnh có trọng số .
Chi phí đường đi giữa hai đỉnh là tổng trọng số các cạnh trên đường đi từ đến . Nếu không tồn tại đường đi từ đến thì chi phí đường đi giữa cặp đỉnh là .
Một cách xóa cạnh được mô tả như sau:
- Chọn hai số nguyên dương thỏa mãn ;
- Xóa tất cả các cạnh được đánh số từ đến .
Cho trước một số nguyên dương . Một cách xóa cạnh được gọi là "đẹp" nếu mọi chi phí đường đi giữa cặp đỉnh bất kỳ (sau khi xóa) không vượt quá . Hai cách xóa cạnh được coi là khác nhau khi có một cạnh trong cách xóa này không có trong cách xóa kia.
Yêu cầu: Đếm số lượng cách xóa cạnh được gọi là "đẹp".
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên ;
- dòng sau, dòng thứ gồm ba số nguyên mô tả cạnh thứ nối đỉnh và đỉnh , có trọng số là . Dữ liệu đảm bảo cạnh tạo thành một cây.
Dữ liệu ra
Một số nguyên duy nhất là số lượng cách xóa cạnh được gọi là "đẹp" (với không có cách xóa nào, in ra ).
Ràng buộc
- ; .
- ; .
Subtasks
- Subtask 1 ( số điểm, số test): .
- Subtask 2 ( số điểm, số test): .
- Subtask 3 ( số điểm, số test): .
- Subtask 4 ( số điểm, số test): cây là một đường thẳng.
- Subtask 5 ( số điểm, số test): không có ràng buộc thêm.
Bài được chấm theo từng test, mỗi test có cùng số điểm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 12 1 2 3 1 4 5 2 3 6 2 5 4 3 6 9 |
9 | Các cách xóa đẹp: . Ví dụ : xóa cạnh , đường đi đắt nhất là từ đỉnh đến đỉnh với chi phí . Còn không đẹp vì đường đi từ đỉnh đến đỉnh có chi phí ; không đẹp vì đường đi từ đỉnh đến đỉnh có chi phí . |
| 5 6 1 2 4 3 4 5 2 3 3 4 5 2 |
6 | Cây là đường thẳng . Xóa một cạnh duy nhất thì luôn còn một đường đi có chi phí lớn hơn (ví dụ xóa cạnh còn đường chi phí ). Mọi cách xóa từ hai cạnh trở lên đều đẹp: . |
Bình luận