I’m stuck on the following dynamic MST problem.
You are given an undirected, weighted graph with N vertices and M edges. The graph will undergo Q dynamic operations. After every operation, you must output the total weight of the current Minimum Spanning Tree (MST). The test data guarantees that an MST always exists after every operation.
Initial Graph:
- Vertices are numbered from 1 to N.
- The graph initially contains M edges.
- Each edge is specified as: u v w representing an undirected edge between u and v with weight w.
Query Types:
U u v w Update or insert an edge. * If an edge (u, v) already exists, change its weight to w. * Otherwise, insert a new edge (u, v) with weight w.
D u v Delete an edge between u and v, guaranteed that it always exist.
Output: After each query, print the total weight of the MST of the current graph. The input guarantees that the graph always remains connected, so an MST always exists.
Constraints: 1 ≤ N ≤ 200000 0 ≤ M, Q ≤ 200000 1 ≤ u, v ≤ N 1 ≤ w ≤ 1e9
Help me in solving in this problem.
