PROBLEM LINK
Author: Fudail Hasan
Tester: Alexey Zayakin
Editorialist: Jakub Safin
DIFFICULTY
HARD
PREREQUISITIES
DFS, dynamic programming on a tree
PROBLEM
You’re given a list E of edges of a graph. For each edge E_i, consider the number f(i) of intervals [L,R] such that L \le i \le R and if the graph contains only edges E_L,\dots,E_R, then E_i lies on a cycle. Compute all f(i).
QUICK EXPLANATION
Compute the minimum R for each L and each i using information for L+1, then use that to compute f(i). Keep a spanning tree using the smallest possible edges, minimum R for all other edges are trivial. The problem reduces to finding the smallest number of a path (for some given paths) covering each edge of the tree; we only need to solve it for all paths ending at the root.
EXPLANATION
Observation number 1: for fixed L,i, let’s take the smallest R such that i is on a cycle for the range [L,R]. Then i is on a cycle for any larger R too. (This is obvious, we’re just adding edges.) That means we only need to compute this smallest R(L) for each L.
First of all, let’s mention that it is possible to compute f(i) independently for each i in linear time. However, we still need them all, so it’s more comfortable to do it differently: for each L, keep incrementing R and adding edges one by one, compute that smallest R(L,i) for all i and use that to directly compute
where we’ll use R(L,i)=M+1 if there’s no such R that edge i lies on a cycle for [L,R].
Doing that in O(M^2) is rather simple. We can add edges one by one. Everytime we add an edge between two different components, we just merge these 2 components, which is even doable in O(M\log{M}) if we’re merging the smaller component into the larger one (standard disjoint set-union). This builds us a tree T_L (actually a forest, but we can add dummy edges). When we’re adding an edge between vertices already in the same component, we know that the smallest R such that this edge i lies on a cycle is R=i; we still need to go through all edges on the path in T_L between vertices it connects and for all of these edges, we know that the maximum R is also i.
However, O(M^2) per each L is too slow. We can speed this up if we notice that it’s better to build T_L first, root it somewhere, compute the 2^k-th ancestor for each k (which allows us to compute LCA-s) and remember the minimum index of those non-tree edges for each vertex v which covers a path to the 2^k-th ancestor for each k.
In the same way as computing LCA, we can split any path into O(\log{M}) sequences of edges. Then, we can use that to compute the minimum index which covers each edge in the tree: if i_1 covers the path from v to its 2^k-th ancestor, i_2 to its 2^{k-1}-st ancestor and i_3 the path between those ancestors, then we can take \mathrm{min}(i_2,i_1) and \mathrm{min}(i_3,i_1) instead of i_2 and i_3 and then forget about i_1. This way, we can put everything from k into k-1 gradually, leaving only k=0, where the paths are just edges in the tree. There are O(M\log{M}) values to process this way.
O(M\log{M}) per each L is good, but probably still too slow. There are 2 parts of the algorithm where it appears and we’ll need to get rid of it in both: constructing T_L (DSU) and computing all minimum R.
Constructing T_L in O(M) is actually pretty easy. When moving from L+1 to L, we add one edge e. We need to find the last edge g on the cycle e created which we’d be adding when constructing T_{L+1} (we can find it e.g. using DFS); this edge should not be in T_L, so we get T_L by removing it and adding e.
What about computing minimum R? For a fixed L, we can’t do much better than the above described O(M\log{M}), but keep in mind that we can use the results from L+1 here as well. Let’s denote the components created after removing that additional edge g by c_1,c_2 (rooted at the endpoints of g); g moves on to become one of those non-tree edges which have R=i.
There are 2 types of paths created by edges \not\in T_L. The first type is only within c_1 or c_2, the second type connects them and therefore must include e. The first such edge gives us R for e; R for all edges \not\in T_L are easily found in O(M). We only have tree edges in c_1 and c_2 to deal with.
Observation 2: R(L,i) \le R(L+1,i). The reason is obvious, if i is on a cycle for [L+1,R], then it’s on a cycle for [L,R] too, since we just added an edge.
Consider the second type of edges. For each tree edge, we can compute the index of the smallest one of them that covers it quickly in linear time – in each component c_{12}, any non-tree edge of this type covers a path from some vertex v_i to the root. We can do bottom-up tree DP computing for each vertex v the smallest edge that covers vertices in its subtree and therefore the edge from it to its parent (except the root, which doesn’t matter anyway). Just take the minimum of its sons and min. i for all edges with v=v_i.
We should know the min. index from edges of the first type too. Fortunately, we don’t need to compute these minima, since we only need to know the minimal R for each edge and if one of these edges gives this minimum for L, then it must have been giving that minimum for L+1 too; thanks to Observation 2, we can simply take R(L,i) to be the minimum of R(L+1,i) and the above computed minimum from type 2 edges. This works because if the min. from type 1 edges for L+1 was x and the min. from type 2 edges was y, then either x \le y and R gives us what we need, or x > y, but then R(L,i) \le y < x. This part clearly also takes just linear time.
Finally we have an algorithm with time complexity O(M) per each fixed L and O(M^2) in total: iterate from L=M to L=1, recompute T_L and all R using the results for L+1 (the initial conditions are trivial) and add M+1-R(i) to f(i) for each edge. The memory complexity is O(M).
Note: we ignored the number of vertices in complexity computations, since we can renumber the edges’ endpoints to \le 2M in O(M\log{M}), which means N=O(M).
AUTHOR’S AND TESTER’S SOLUTIONS
Setter’s solution: Will be uploaded soon.