Kho báu
Đề bài
Mô tả
Một vùng biển bao gồm hòn đảo đánh số từ đến và được kết nối bởi tuyến đường biển. Từ một hòn đảo bạn có thể đến được mọi hòn đảo khác chỉ qua các tuyến đường này.
Mỗi hòn đảo thuộc địa phận của chính xác một quốc gia, các quốc gia được đánh số từ đến . Hòn đảo thuộc địa phận của quốc gia . Lưu ý một quốc gia có thể bao gồm bất kì tập con các hòn đảo nào, và có thể bạn không thể di chuyển giữa hai hòn đảo cùng quốc gia chỉ bằng cách đi qua các hòn đảo cùng quốc gia khác.
Bạn là một thợ săn kho báu và đang sinh sống ở hòn đảo . Mỗi hòn đảo có một mức thuế nhất định cho mỗi kho báu bạn mang qua. Ở hòn đảo , mức thuế là đồng.
Bạn được biết hai loại sự kiện sau có thể xảy ra:
- Hòn đảo trở thành địa phận của quốc gia .
- Có kho báu sẽ xuất hiện ở các hòn đảo , khi đó bạn sẽ di chuyển đến tất cả các hòn đảo này và mang kho báu ở từng hòn đảo về hòn đảo (theo đường đi duy nhất trên các tuyến đường biển). Sau đó bạn sẽ chọn một hòn đảo bất kì thuộc địa phận của quốc gia và bạn sẽ chỉ phải trả thuế đồng với là số lượng kho báu bạn mang qua hòn đảo . Kho báu xuất hiện ở hòn đảo được tính là mang qua chính hòn đảo và mọi hòn đảo trên đường từ về hòn đảo (kể cả hòn đảo ).
Với mỗi sự kiện loại , bạn cần tính mức thuế lớn nhất mà bạn phải trả trên một hòn đảo bất kì thuộc quốc gia , tức là giá trị lớn nhất của trên các hòn đảo đang thuộc quốc gia . Nếu không có hòn đảo nào thuộc quốc gia thì mức thuế bạn phải trả là .
Các sự kiện loại có hiệu lực lâu dài: chúng ảnh hưởng đến mọi sự kiện xảy ra sau đó.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và : số lượng hòn đảo và số lượng sự kiện.
- Dòng thứ hai chứa số nguyên , trong đó có nghĩa là có một tuyến đường biển giữa hòn đảo và hòn đảo .
- Dòng thứ ba chứa số nguyên , trong đó hòn đảo thuộc địa phận của quốc gia .
- Dòng thứ tư chứa số nguyên : mức thuế tương ứng của từng hòn đảo.
- dòng tiếp theo, mỗi dòng bắt đầu bằng số nguyên là loại sự kiện:
- Nếu , tiếp theo là hai số nguyên và , có nghĩa là trở thành địa phận của quốc gia .
- Nếu , tiếp theo là hai số nguyên và , sau đó là số nguyên , trong đó là quốc gia mà bạn phải chọn một hòn đảo để đóng thuế, là số lượng hòn đảo có kho báu, và là các hòn đảo chứa kho báu. Bộ test đảm bảo các trong cùng một sự kiện đều khác nhau và tổng trong các sự kiện loại không vượt quá .
Dữ liệu ra
Với mỗi sự kiện loại , theo thứ tự xuất hiện, in ra trên một dòng mức thuế lớn nhất mà bạn phải đóng. Nếu không có hòn đảo nào thỏa mãn thì in ra .
Ràng buộc
- , .
- .
- , .
- ; , các trong một sự kiện đôi một khác nhau.
- Tổng trong các sự kiện loại không vượt quá .
Subtasks
- Subtask 1 ( số điểm): .
- Subtask 2 ( số điểm): không có sự kiện loại và với mọi .
- Subtask 3 ( số điểm): không có sự kiện loại .
- Subtask 4 ( số điểm): .
- Subtask 5 ( số điểm): .
- Subtask 6 ( số điểm): không có ràng buộc gì thêm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 1 2 2 1 1 3 3 2 3 10 7 2 3 2 3 4 2 1 2 4 3 1 3 1 2 1 2 3 4 |
10 6 10 |
Sự kiện thứ nhất: kho báu ở đảo và , đóng thuế ở quốc gia gồm đảo và , mỗi đảo được mang kho báu qua đúng một lần, đáp án . Sự kiện thứ hai: quốc gia gồm đảo và , cả hai được mang kho báu qua hai lần, đáp án . Sự kiện thứ ba: đảo chuyển sang quốc gia . Sự kiện thứ tư: quốc gia gồm đảo ; đảo được mang qua hai lần, đảo một lần, đáp án . |
| 5 5 1 1 3 3 2 1 2 1 1 4 9 1 5 6 2 2 3 4 5 2 2 1 2 4 5 1 5 3 2 1 3 4 5 2 2 4 1 1 |
12 6 9 0 |
Sự kiện 1: , , quốc gia gồm đảo và , đáp án . Sự kiện 2: quốc gia gồm đảo với lần lượt , đáp án . Sự kiện 3: đảo rời quốc gia . Sự kiện 4: đáp án (đảo không còn tính). Sự kiện 5: quốc gia không có hòn đảo nào, đáp án . (Ví dụ này không có trong đề gốc.) |
Bình luận