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.
Offline solution is described here: https://codeforces.me/blog/entry/105192
Another solution (also offline) that I could think of is DCP offline + link-cut tree / weighted dsu which will result in $$$O((q+m) \log(q)\log(n))$$$ complexity.
Can you explain the approach?
For each edge find segments in time where it exists. There are $$$q$$$ points in time where something changes so the total number of such segments across all edges is $$$O(q + m)$$$.
Then build segment tree over $$$q$$$ time points and put all segments in it. Each segment will be splitted in $$$O(\log(q))$$$ subsegments and putted in corresponding vertexes in segtree. In total all $$$O(q + m)$$$ segments will be splitted in $$$O((q + m)\log(q))$$$ subsegments and stored in segtree.
Now do dfs over segtree. Upon entering vertex insert all edges that are stored in that vertex into a data structure that supports edge insertion while maintaining MST. Upon leaving vertex just undo all operations you did in your data structure.
Such data structure can be:
link-cut tree
weighted dsu
Both take $$$O(\log(n))$$$ per query but most likely weighted dsu gonna outperform LCT since weighted dsu:
has much smaller constant
seems to have non-amortized complexity while LCT has amortized one which might result in degradation of time complexity up to $$$O((q + m)\log(q)n)$$$ on some carefully designed input data
Sahi hai, aur bhi kuch batao sir