PROBLEM LINK:
Author: Devendra Agarwal
Tester: Kevin Atienza
Editorialist: Kevin Atienza
PREREQUISITES:
Heavy-light decomposition, Minimum spanning tree, range queries
PROBLEM:
You’re given a weighted undirected graph. For each edge, output the minimum spanning tree such that the edge is removed. If removing the edge disconnects the graph, output -1.
QUICK EXPLANATION:
Find an MST T. For every edge e not in T, the answer is just the cost of T. For every edge e in T, let R[e] be a pointer to another edge, initially null.
Compute the heavy-light decomposition of T, and in each heavy path, set up a segment tree which can perform the following operation quickly:
Given an edge e' = (u,v), set R[e]:=e' for all edges e in the path from u to v.
The answer for every edge e in T is w(T) - w(e) + w(R[e]), but if R[e] is null, then it is -1.
EXPLANATION:
Let’s write the weight function of the graph G as w, so w(e) is the weight of the edge e. Being very loose with notation, if E' is a set of edges of G, then we write w(E') as the sum of the weights of the edges in E', and if G' is a subgraph of G', then we write w(G') as the sum of the weights of the edges in G'.
Let’s find any minimum spanning tree (MST) first (for example, using Kruskal’s algorithm), say T. Now, if an edge doesn’t belong to T, then answer is just the cost of T, because this is the best MST we can create. Thus, we only need to answer the query for each edge in T.
When an edge is removed from T, two subtrees are created. In order to create a new spanning tree, we must connect these two subtrees again with a node. Since we want the minimum spanning tree, we must use the edge with the lowest weight. Thus, we have the following (trial) algorithm for finding a minimum spanning tree that doesn’t include some edge e (assuming it is in T):
- Remove e edge, so T is disconnected into two components.
- Find the lowest-weight edge e' connecting the two components back. The new MST is now the weight of e' plus the weight of the remaining edges of T. If no such edge e' exists, the answer is -1.
This is a greedy choice, so the new spanning tree we get isn’t necessarily the minimum spanning tree. There might be another spanning tree that can be acquired with another method. So, is this greedy choice correct? If you’re familiar with how the usual MST algorithms (Prim, Kruskal) work, then this might be intuitive enough for you. If not, you can see a proof here. (Or you can try proving it yourself.)
So the answer for edge e is now: w(T) if e is not in T, and w(T) - w(e) + w(e') if e is in T. Thus after computing T and w(T), we only need to compute e' for each e. Let’s call the edge e' the lowest-weight replacement edge of e, where we define a replacement edge as an edge connecting the two subtrees generated when e is removed from T.
For an edge e in T, let’s try to compute its lowest-weight replacement edge e'. One way to do it is with an equivalent characterization of the replacement edge, which we derive as follows. Removing the edge e separates T into two trees T_1 and T_2. The only way to travel from T_1 to T_2 in T is through the only bridge between them, which is e. So, if (u,v) is an edge such that u \in T_1 and v \in T_2, then the unique path from u to v in T must pass through e. Thus, an alternative characterization of a replacement edge is the following: an edge (u,v) such that the path from u to v in T passes through e.
So to find the lowest-weight replacement edge, we must somehow figure out for each edge (u,v) whether the path from u to v in T passes through e. Now only that, we must find the minimum-weighted such edge. We also need to do this for all edges e in T. One way to do this quickly is to “invert” the operation. Instead of computing the lowest-weight replacement edge e' for each edge e in T, we compute for each edge e' not in T all the edges e in T whose lowest-weight replacement edge is e'. This can be done as follows:
- For each edge e in T, we write R[e] as the best replacement edge of e so far, initialized to be null.
- Sort all edges e' not in T in decreasing order of weight, and iterate through them. For each edge e' = (u,v), we set R[e] := e' for all edges e in the path from u to v.
- After this, R[e] is now the lowest-weight replacement edge of e for every e in T.
This algorithm is correct because we are iterating through all the $e’$s in decreasing order of weight, which means the final value written at R[e] is the lowest-weight replacement edge. It is also clear that for each edge e, all its replacement edges occupy R[e] at least once.
Thus, to solve the problem within the time limit, we must be able to perform the following operation quickly in a tree T, where each edge e has a value R[e] associated with it:
Given two nodes (u,v) and some object e', set R[e] := e' for all edges e in the path from u to v.
How can we do this quickly? This is easy to do with a segment tree with lazy propagation if T is just a path graph, and each operation will take O(\log N) time. But if T is not a path graph, there’s a way to partition the edges into paths such that every simple path through T passes through at most O(\log N) paths in the partition. The heavy-light decomposition is one such example.
With such a partition, we can set up a segment tree for each path in the partition, and split a query (u,v) into O(\log N) separate queries in the segment trees, so each operation takes O(\log N)\cdot O(\log N) = O(\log^2 N).
In fact, since we perform the queries offline (because we can compute all queries to each path before processing any of them), we actually don’t need a segment tree with lazy propagation for each path to process all queries to it! One way to do so using only tree sets is implemented in the tester’s solution.
Time Complexity:
O(E \log^2 N)