PROBLEM LINK:Author: Pawel Kacprzak DIFFICULTY:MEDIUM PREREQUISITES:Graph theory, Minimum Spanning Tree, Kruskal's algorithm PROBLEM:This problem is all about Minimum Spanning Tree, which we call $MST$ here. For a given graph $G$ with $N$ vertices and $M$ weighted edges, the goal is to handle $Q$ queries. Each query can either assign $0$ weight to given existing edge in $G$ or assign to a given edge its original weight, or ask for the weight of $MST$ of the current graph $G$. QUICK EXPLANATION:Take a closer look at how does Kruskal’s algorithm work and notice that the answer for each query asking for the weight of the current $MST$ can be computed by running Kruskal’s algorithm only on edges with zero weight and edges in the initial $MST$ of $G$. EXPLANATION:Subtask 1In the first subtask we have $N \leq 200, M \leq 2000$ and $Q \leq 2000$, so we can just keep track of the current weights of the edges while performing queries and for each query asking for the weight of the current $MST$, we can run any fast algorithm computing $MST$ from the scratch, for example Kruskal’s algorithm. This solution has time complexity of $O(Q \cdot f(N, M))$, where $f(N, M)$ is the complexity of used $MST$ algorithm on a graph with $N$ vertices and $M$ edges. Notice that this results in $O(Q \cdot M \cdot \log^*(M))$ time for Kruskal's algorithm even when full sorting is performed only at the beginning. Subtasks 2 and 3In these subtasks we have $N \leq 2000$, $M \leq 2 \cdot 10^5$ and $Q \leq 20000$. The following approach can be used to solve both of these subtasks, the only difference is that in the last subtask one have to handle restoring original weights of edges, which is just a little bit more straightforward implementation. Let’s first compute $MST$ of the initial graph before performing any queries and let $T$ be this $MST$. The crucial observation is that at any point while handling the queries, the weight of the $MST$ of the current graph can be computed by running Kruskal’s algorithm on edges with zero weight at this point and edges of $T$. Why is this observation correct? Well, if we take a closer look at how does this algorithm work, we can see that it iterate over a list of given edges in ascending order of their weights and put the current edge into the result if and only if it connects not yet connected components of $G$. So if we run it on edges with zero weight and edges from $T$, it will merge some components using some of these zero edges first and then try edges from $T$ if necessary. Since the algorithm is only merging components, it follows that no edge not it $T$ with nonzero edge at this point will be used by the algorithm, because after processing edges with zero weights, some edges from $T$ might not be needed, but if any two components still require to be merged, the algorithm will do it with an edge from $T$ just as it did in the initial graph. Thus in order to solve the problem, one can maintain the list of edges with zero weights updating it when necessary  this can be done in $O(1)$ time if for example a linked list is used, and for each query asking for the weight of the current $MST$ run Kruskal’s algorithm on at most $O(Q + N)$ edges. Theoretically this results in $O(Q \cdot (Q + N) \cdot \log^*(N))$ complexity, but notice that in order for $K$ zero edges to be processed by the algorithm, we have to perform $K$ queries adding them first, so the factor of $Q^2$ is divided by some constant of at least $4$ here. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 31 Dec '16, 19:35

The practice link gives "problem not visible" message. When will the problems be added to the practice section? answered 31 Dec '16, 23:41

Please add the problem to the practice section. answered 01 Jan, 02:19

I thought this would time out. Is there some upper bound on value of n in O(n) such that it passes tests in 't' seconds? answered 02 Jan, 05:06

Great problem @pkacprzak but I am having hard time understanding why is it not giving TLE. I have used following approach: answered 03 Jan, 18:18
Hi, I've just read your code. The only reason I see it passes, is that when you're processing query 3, you break early from the loop (because you added already n1 edges), let's say it happens after O(n) iterations. If this is the case, then probably and unfortunately tests are not as strong as the should and it's my fault then. You can put some assertions to check how many maximum iterations of this loop are performed to verify this hypothesis. Thanks
(03 Jan, 20:15)
