PROBLEM LINK:
Author: Constantine Sokol
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu
DIFFICULTY:
Hard
PREREQUISITES:
Segment Tree, Heavy Light Decomposition, Flow
PROBLEM:
Given a graph G, consisting of N vertices and M edges, each edge has a positive capacity and each vertex of G belongs to at most one simple cycle.
You task is to implement a data structure, which can process the following queries efficiently:
- 0 S T: find the maximum flow in G in case the source is S and the sink is T;
- 1 X NEW_CAPACITY: make the capacity of X'th edge equal to NEW_CAPACITY.
SOLUTION OUTLINES:
Link1: Heavy Light Decomposition
Link2: Heavy Light Decomposition
If you don’t know about HLD you can read about it on the previous editorials etc. :).
Firstly, let’s assume that the graph given to us consists of a single cycle. Than the solution is obvious: there are only two path between every two distinct vertices. We can simply maintain a segment tree of edges and that’s it.
Secondly, let’s assume that the graph given to us is a tree. That the solution is obvious as well: there’s a single path between every two distinct vertices. We can use Heavy-Light Decomposition of tree in order to process all the queries and that’s it.
OK, now let’s go back to the problem as it is.
Tester’s Approach
We consider a cycle as a node, then graph will be a tree. After this we do HL-decomposition, then each component will be like a (upper component) – cycle – cycle – cycle – cycle. (here cycle = a cycle or an ordinary node). We use a segment tree for each component of HLD, and we also use a segment tree for each cycle. Then we can calculate the maximum flow from some node to the nearest node of upper component of HLD in O(log N). And of course, we can calculate the maximum flow from some node to some node, if both nodes are in the same component in O(log N). The depth of HLD is O(log N), so we can calculate the maximum flow in O( (log N)^2 ).
The modification query is not difficult in this approach.
If the edge is in cycle, we modify this cycle, and then modify HLD.
Otherwise, we just modify HLD.
It will be done in O(log N).
Author’s Approach
Firsly, let’s make our graph rooted(let’s assume that the first vertex is the root). Now the processing of the queries is splited into two parts:
- We need to raise both vertices A and B to the same cycle.
- Then, just simply solve the problem of a cycle(described before).
So, the problem is to raise a single vertex to a cycle.
Let’s do this for each cycle: we have a cycle 1 - 2 - 3 - 4 - … - K, which consists of K vertices. Then, let’s transform it into K - 1 edges 1 - 2, 1 - 3, 1 - 4, …, 1 - K, where the capacity of edges 1 - L(for 1 < L <= K) is equal to the size of the flow, that can stream through the cycle from vertex L to the vertex 1.
If we have no modification queries, than the problem is easy: we simply transform our graph into a tree and then process all the queries the way described above.
But the problem is that we have modification queries. 
If we modify the capacity of an edge, that doesn’t belong to any cycle(let’s call it a tree edge), then we can simply maintain such edges with HLDOT.
If we modify the capacity of an edge, that does belong to a cycle(let’s call it a cycle edge), then we should:
A) Update the corresponding segment tree with the new capacity.
B) Update the capacity of all (K - 1) edges, that we built for the cycle of this cycle edge.
The problem is with B). If we update the capacity of a cycle edge, that belongs to a big cycle, then we should update a lot of edges and can lead to the TLE verdict.
But there are not so many big cycles. Let’s call a cycle BIG if it contains at least sqrt( N ) vertices and SMALL otherwise. Then, for each small cycle we can simply update all the (K - 1) edges. For big cycle we won’t maintain the edges in our HLDOT. We will store them separately. When we need to process a flow-query, we can simply loop through all the big cycles and calculate the size of the flow.
So, total complexity:
Preprocessing: O( N log N )
Change-query: O( log N ) for an tree edge, O( K * log N ) for an cycle edge of a small cycle, O( log N ) for an cycle edge of a big cycle.
Flow-query: O( ( log N ) ** 2 + T * log N ), where T equals to the number of big cycles.
The complexity of change-query won’t exceed sqrt( N ) * log N.
The complexity of flow-query won’t exceed sqrt( N ) * log N as well.
So, the solution runs in O( N log N + Q * sqrt( N ) * log( N ) )
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution
Tester’s solution
