Cây khung khi mất cạnh

Buổi 20 — Cây khung nhỏ nhất
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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 -1 nế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$
Draft saved