PROBLEM LINK:
Author: Kevin Charles Atienza
Testers: Istvan Nagy
Editorialist: Praveen Dhinwa
DIFFICULTY:
hard
PREREQUISITES:
tree dp, merging smaller component with largest component
PROBLEM:
You are given a graph network consisting of n nodes and m edges. i-th person uses color c_i. For each vertex i, you have to answer following quantity - assume If we remove i-th vertex, how many pairs of vertices with same colors will get disconnected. We call such pairs sad pairs.
QUICK EXPLANATION:
Solve the problem on a tree
Convert the given graph into block cut tree and now apply the algorithm for solving the problem on a tree.
EXPLANATION:
Solve on a tree
Let us first simplify the problem by solving it on a tree. Note that each vertex of tree will be an articulation point - a vertex in a connected graph is considered articulation point if removing it from the tree divides the graph into more than one disconnected components. To be more precise, all the non-leaf nodes will be articulation points.
Let us root the tree at any vertex (say vertex 1). Let us understand what will be number of sad pairs if we removing vertex 1. Let there be child children of vertex 1. Consider a color c, Let cnt_1, cnt_2, \dots cnt_{child} denote the number of colors c all the children subtrees of vertex 1. Now number of sad pairs for this color will be sum of cnt_i * cnt_j for i < j childs.
Directly iterating over i, j will take O({child}^2) time. Instead, for each j, we can find sum of terms multiplied with cnt_j efficiently. Essentially it will be cnt_1, cnt_2, \dots, cnt_{j - 1}. You can compute this quantity by maintaining a prefix sum. Pseudo-code follows.
sum[0] = 0
For (j = 2; j ≤ child; j++)
sad += cnt[j] * (sum[j])
sum[j] += cnt[j]
So, now we know to how to find sad pairs for a given color. Finally total sad pairs will be sum of sad pairs for each distinct color.
Let us maintain a map<int, int> for each node v in the tree - denoting the counts of various color in the subtree of v. So, the key will correspond to color and the value will denote the count of corresponding color in the subtree of v.
Now a we do a dfs from starting node 1. In the dfs, we will maintain a map as described above. See the pseudo code
void dfs(from, parent):
childs = {};
for each neighbour to of from:
if to = parent:
continue
childs.add(to);
dfs(to, from)
// Now at this stage, we will have maps for the childs computed.
// Let us create corresponding map for vertex from using the child maps.
map fromMap
for each child c in childs:
add map corresponding to c to fromMap
Time complexity of this solution will be O(n^2) and similarly space complexity will also e O(n^2). We need to optimize both space and time complexity.
Now, we will use a trick of merging smaller subtrees into the largest one at each node. For a very clear understanding of this trick, please see this nice tutorial. If possible, also solve the problems provided in the practice section.
For each node, let us call the child whose subtree has largest number of nodes as heavy child (if there are more than one childs, pick any of those). Call the remaining children as lighter children.
While computing map for a node, we will merge the maps of lighter children into the map of heavy child. Now, the map corresponding to the current node will be same as that of heavy child.
void dfs(from, parent):
childs = {};
heavy = none;
maxSize = 0
for each neighbour to of from:
if to = parent:
continue
dfs(to, from)
childs.add(to);
if size[to] >= maxSize:
maxSize = size[to]
heavy = to
// Now at this stage, we will have maps for the childs computed.
// Let us create corresponding map for vertex from using the child maps, by merging the smaller maps into heavy child.
let heavyMap = map corresponding to heavy map; // Please note that this is not equivalent to creating a copy. It is reference to that map.
for each child c in childs:
if c != heavy:
for each (key, value) pair in map[c]:
heavyMap[key] += value
map[from] = heavyMap; // Please note that this is also not a copy. You have to make sure that this is a reference. In other words, make sure that memory used for map is same as that of heavyMap.
Let us consider an edge of the tree (u, v) - u is parent of v. We will call the edge heavy if v is a heavy child of u, light otherwise.
Let us estimate time and space complexity of this approach. The key, value pair maintained for a color in vertex v is moved into the heavy subtree of parent u, if u is light child, i.e. the movement of (key, value) pair is happending across the light edge.
Number of light edges in any path from root 1 to any other vertex can be at max \mathcal{O}(log n). Hence, it means that each key will be moved at most log n times.
Hence, it means that time complexity of this approach will be \mathcal{O} (n log n) * log n \text{(for operations on map)}.
Note that space complexity of this approach is \mathcal{O}(n log n) too. Please note the very crucial point that when you have merged the ligher subtrees into heavy subtree, then you don’t have to create an entirely new map having the content of merged subtree. You can just reuse the memory that you had allocated for heavy subtree. You can implement this by either using references or pointers etc. Please see various solutions for understanding details.
Solve the problem on a graph
We will find all the articulation points of the graph. Construct block-cut tree corresponding to the graph using these articulation points. Now, on this block-cut tree, we can apply the same algorithm as previous one to solve the problem. Note that you don’t need to construct the tree explicitly, you can use the tree strcuture implicitly, see the code of tester for details.
Please note that I have skipped some details on how to compute the sad pairs using the maps created for each subtree. These details should be relatively easier to figure out.
Time Complexity:
\mathcal{O}(n + m) (for finding block-cut tree) + \mathcal{O}(n * {log n}^2) for solving the problem on created tree.
