Lộ trình
Đề bài
Mô tả
Một quốc gia có thành phố, được đánh số từ đến . Các thành phố được kết nối bằng đúng tuyến đường hai chiều. Hệ thống giao thông được xây dựng sao cho giữa hai thành phố bất kỳ luôn tồn tại duy nhất một đường đi. Nói cách khác, mạng lưới giao thông của quốc gia tạo thành một đồ thị dạng cây, mỗi tuyến đường nối trực tiếp hai thành phố không qua một thành phố trung gian nào cần đúng một ngày để đi qua.
Một đội công tác chuyên trách về kiểm định hạ tầng được giao nhiệm vụ đánh giá chất lượng của một dự án giao thông liên vùng, toàn bộ nhiệm vụ được chia thành mức theo trình tự thực hiện, đánh số từ đến . Thành phố thứ có mức nhiệm vụ là . Trong đó, thành phố có mức nhiệm vụ thấp nhất là , thành phố có mức nhiệm vụ cao nhất là .
Một lộ trình hợp lệ là một lộ trình đi qua một dãy các thành phố thỏa mãn đồng thời các điều kiện sau:
- và .
- Với mỗi từ đến , thành phố có nhiệm vụ mức .
Đội công tác thực hiện nhiệm vụ xuất phát từ lần lượt đi tới . Một chặng đường thực hiện nhiệm vụ đi từ thành phố đến thành phố được tính là hoàn thành khi là điểm kết thúc của chặng đường đó với đường đi là ngắn nhất . Việc đi ngang qua một thành phố trung gian nào đó trong lúc di chuyển giữa hai thành phố và không được tính là hoàn thành nhiệm vụ, kể cả khi thành phố đó có mức nhiệm vụ cao hơn.
Gọi là số ngày ít nhất để đi từ thành phố tới thành phố , tức độ dài đường đi ngắn nhất giữa chúng trên cây. Thời gian hoàn thành của một lộ trình hợp lệ là tổng số ngày di chuyển của toàn bộ hành trình, cụ thể bằng:
Yêu cầu: Hãy tính tổng thời gian hoàn thành của tất cả các lộ trình hợp lệ. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho .
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên dương và ;
- Dòng thứ hai chứa số nguyên dương tương ứng là mức nhiệm vụ của từng thành phố (dữ liệu đầu vào đảm bảo luôn tồn tại lộ trình hợp lệ);
- dòng tiếp theo, mỗi dòng chứa hai số nguyên dương và mô tả một tuyến đường nối hai thành phố và .
Dữ liệu ra
Gồm một số nguyên không âm là tổng thời gian hoàn thành của tất cả các lộ trình hợp lệ, lấy phần dư khi chia cho .
Ràng buộc
- , , ; luôn tồn tại lộ trình hợp lệ.
Subtasks
- Subtask 1 ( số điểm): .
- Subtask 2 ( số điểm): .
- Subtask 3 ( số điểm): .
- Subtask 4 ( số điểm): Cây có dạng đường thẳng.
- Subtask 5 ( số điểm): Không có ràng buộc gì thêm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 4 1 2 3 3 2 4 3 1 3 2 3 4 3 6 5 6 |
24 | Các thành phố mức là , mức là . Có bốn lộ trình: (), (), (), (). Tổng là . |
| 5 3 1 2 1 2 3 1 2 2 3 3 4 4 5 |
8 | Ví dụ thêm (không có trong đề gốc). Lộ trình luôn bắt đầu ở thành phố (thành phố cũng có mức nhưng không được chọn làm ): dài , dài . |
Bình luận