Khởi động đen
Đề bài
Mô tả
Một cơn bão đã làm sập lưới điện khu vực, mọi trạm biến áp đều mất điện. Lưới điện gồm trạm biến áp, đánh số từ đến , và đường dây truyền tải. Mỗi đường dây nối hai trạm khác nhau và có độ dài là một số nguyên dương. Từ mỗi trạm có thể đi đến mọi trạm khác theo các đường dây, nên các đường dây tạo thành một cây. Khoảng cách giữa hai trạm là tổng độ dài các đường dây trên đường đi duy nhất giữa chúng.
Trạm được trang bị một bộ khuếch đại có bán kính . Ngay khi trạm có điện, nó cấp điện cho mọi trạm có khoảng cách tới trạm không quá . Các trạm vừa có điện lại cấp điện cho các trạm khác theo cùng quy tắc, và cứ thế tiếp tục cho đến khi không còn trạm nào mới có điện. Nói riêng, một trạm có bán kính không cấp điện cho trạm nào khác.
Để khởi động lại lưới điện, người vận hành bật máy phát khẩn cấp của một số trạm, các trạm này có điện ngay từ đầu. Hãy tìm số trạm ít nhất cần bật máy phát để cuối cùng mọi trạm đều có điện.
Dữ liệu vào
- Dòng đầu tiên chứa một số nguyên (): số trạm biến áp.
- Dòng thứ hai chứa số nguyên (): bán kính của các bộ khuếch đại.
- Mỗi dòng trong dòng tiếp theo chứa ba số nguyên , và (, , ), mô tả một đường dây độ dài nối hai trạm và . Dữ liệu bảo đảm các đường dây tạo thành một cây.
Dữ liệu ra
In ra một số nguyên duy nhất: số trạm ít nhất cần bật máy phát.
Ràng buộc
- .
- .
- , , ; các đường dây tạo thành một cây.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 4 3 0 5 2 0 7 1 2 4 2 3 3 2 4 5 4 5 2 4 6 6 6 7 1 |
2 | Bật máy phát ở trạm và trạm . Trạm cấp điện cho trạm (khoảng cách ) và trạm (khoảng cách đúng bằng ). Trạm cấp điện cho trạm và trạm , trạm cấp điện cho trạm . Không trạm nào cấp điện được cho trạm hay trạm ; chẳng hạn trạm cách trạm một khoảng nhưng bán kính chỉ là . Vì vậy cần cả hai máy phát. |
| 4 10 10 0 0 1 2 10 2 3 10 3 4 1 |
2 | Trạm và trạm cấp điện cho nhau, nên một máy phát ở một trong hai trạm này làm trạm , và có điện. Trạm cách trạm một khoảng , nhưng bán kính của trạm bằng , nên trạm cần máy phát riêng. |
Bình luận