Cây khung khi mất cạnh
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị vô hướng liên thông gồm $N$ đỉnh và $M$ cạnh có trọng số, đánh số từ $1$ đến $M$.
Cho $Q$ truy vấn độc lập, mỗi truy vấn cho một chỉ số cạnh idx. Hãy tìm tổng trọng số cây khung nhỏ nhất (MST) của đồ thị sau khi xóa bỏ cạnh idx. Nếu việc xóa cạnh idx làm đồ thị mất tính liên thông, in ra -1.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, Q$ ($1 \le N, Q \le 10^5, N - 1 \le M \le 2 \cdot 10^5$).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i, v_i, w_i$ ($1 \le u_i, v_i \le N, 1 \le w_i \le 10^9$).
- $Q$ dòng cuối cùng, mỗi dòng chứa một số nguyên
idx($1 \le \text{idx} \le M$).
Dữ liệu ra
- In ra $Q$ dòng, mỗi dòng là trọng số MST sau khi xóa cạnh tương ứng, hoặc
-1nếu đồ thị bị ngắt kết nối.
Ví dụ
| Input | Output |
|---|---|
| 4 5 5 1 2 1 2 3 2 3 4 3 1 4 4 2 4 5 1 2 3 4 5 |
9 8 7 6 6 |
| 3 2 2 1 2 5 2 3 7 1 2 |
-1 -1 |
Giới hạn
- $1 \le N, Q \le 10^5$
- $N - 1 \le M \le 2 \cdot 10^5$
- $1 \le w_i \le 10^9$
Community Discussion