Bài toán cây khung tuyệt vời
Đề bài
Mô tả
Cho một đồ thị vô hướng liên thông có trọng số gồm đỉnh và cạnh. Đồ thị không có khuyên, và giữa hai đỉnh bất kỳ có không quá một cạnh.
Một cạnh được gọi là tuyệt vời nếu có ít nhất một cây khung nhỏ nhất chứa cạnh đó.
Có truy vấn. Mỗi truy vấn thêm một cạnh mới vào đồ thị, sau đó bạn cần đếm số cạnh tuyệt vời của đồ thị mới. Lưu ý rằng một cạnh đã được thêm thì ở lại trong đồ thị mãi mãi.
Cây khung nhỏ nhất của một đồ thị vô hướng liên thông có trọng số là một tập con các cạnh nối tất cả các đỉnh với nhau, không tạo chu trình và có tổng trọng số nhỏ nhất có thể.
Ví dụ, xét đồ thị đỉnh với các cạnh , , , , , , , , , , , (mỗi bộ là một cạnh nối và với trọng số ). Đồ thị này có cây khung nhỏ nhất: cả hai đều chứa các cạnh , , , , , và cây thứ nhất chứa thêm , cây thứ hai chứa thêm . Đồ thị có cạnh tuyệt vời: , , , , , và .
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và , số đỉnh và số cạnh của đồ thị.
- dòng tiếp theo, dòng thứ chứa ba số nguyên , , : có một cạnh nối hai đỉnh và với trọng số trong đồ thị ban đầu.
- Dòng tiếp theo chứa số nguyên , số truy vấn.
- dòng tiếp theo, mỗi dòng chứa ba số nguyên , , mô tả một truy vấn thêm cạnh nối hai đỉnh và với trọng số .
Dữ liệu đảm bảo rằng lúc đầu và sau mỗi truy vấn, đồ thị luôn liên thông và không có hai đỉnh nào được nối bởi nhiều hơn một cạnh.
Dữ liệu ra
Với mỗi truy vấn, in ra một dòng chứa số cạnh tuyệt vời của đồ thị sau truy vấn đó.
Ràng buộc
- .
- , , .
- .
- , , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 10 2 7 1 5 6 3 4 5 4 6 7 5 3 4 5 1 7 6 1 2 9 1 3 9 1 4 9 1 5 9 2 1 6 9 2 3 2 |
6 7 |
Sau truy vấn thứ nhất, các cạnh tuyệt vời là , , , , , . Sau truy vấn thứ hai, đồ thị chính là đồ thị trong phần mô tả. |
| 3 2 1 2 5 2 3 5 1 1 3 5 |
3 | Ví dụ bổ sung (không có trong đề gốc). Ba cạnh cùng trọng số tạo thành một chu trình, mỗi cạnh đều nằm trong một cây khung nhỏ nhất nào đó. |
Bình luận