Note: it can be shown that ~M \le \frac{3}{2} \times N~ for any cactus graph. Thus, we can say that ~M \in \mathcal{O}(N)~.

Subtask 1

One solution is to run an All Pairs Shortest Path algorithm on an unweighted graph (such as breadth first search from each vertex), and check all pairs of vertices that are the same colour. Here we will provide an alternate solution that is useful for later subtasks.

We can perform breadth first search from multiple sources from the vertices of a colour, which takes ~\mathcal{O}(N)~ time for each of the ~N~ colours. However, unlike the usual breadth first search algorithm, for each vertex, we will want to find the minimum distance to the 2 closest source vertices. The answer can then be found by checking all vertices and taking the sum of the 2 distances.

Time Complexity: ~\mathcal{O}(N^2)~

Subtask 2

For the second subtask, recall that the distance between vertices ~u~ and ~v~ is ~d(u) + d(v) - 2 \times d(lca(u, v))~ where ~d(u)~ is the distance from the root of the tree (which we can choose arbitrarily and compute with a single depth first search) to vertex ~u~, and ~lca(u, v)~ is the lowest common ancestor of vertices ~u~ and ~v~, which can be computed in multiple ways, such as heavy-light decomposition, binary lifting, and range minimum queries. Using range minimum queries will be helpful for the later subtasks, as it takes ~\mathcal{O}(N \times \log N)~ time for precomputation, and ~\mathcal{O}(1)~ for each query.

To deal with the fact that the graph is a cactus, we can do the following. First, find the cycles in the graph by performing a depth first search, and keeping track of the vertices currently on the stack. Assign each cycle a root, based on the depth first search order. Note that multiple cycles may share a root. Remove all edges in the cycle, and create new edges from each vertex in the cycle to the root of the cycle. The weight of this edge is the shortest path between them using the cycle edges. The new graph is now a weighted tree.

Now, we can compute the distance by finding the lowest common ancestor the same way as before, but if the lowest common ancestor is the root of a cycle, then an additional check needs to be performed. Consider the shortest path between vertices ~u~ and ~v~ in the newly formed tree. Each vertex has a non overlapping path to the lowest common ancestor. Each path has at most one vertex that is a direct child of the lowest common ancestor. If this vertex exists for both paths, and both vertices are part of the same cycle, then it is possible that there is a shorter path between them that does not go through the cycle's root. Determining whether the two vertices are part of the same cycle can be done by maintaining a mapping from a pair of vertices of the cycle root and vertex in the cycle, with a unique cycle id. Finding the direct child of a lowest common ancestor can be done by computing an Euler tour of the tree, and binary searching the adjacency list (or alternatively, by using a second sparse table). From here, we can take the minimum of all paths for pairs of vertices of that colour as the answer.

Time Complexity: ~\mathcal{O}(N \times \log N)~

Subtask 3

For the third subtask, we can group colours into two categories. Let ~V_c~ be the number of vertices of colour ~c~. We will divide the colours into ~V_c > B~ and ~V_c \le B~ (we will determine ~B~ later). It's easy to see that there can be at most ~\frac{N}{B}~ colours of the first type. Thus, we can use the idea from the first subtask for each of these colours, which will take ~\mathcal{O}(\frac{N^2}{B})~ time. For the second type, we can use the idea from the second subtask, except we do not have to worry about the graph being a cactus. We will compute the distance between all distinct pairs of vertices of that colour. Since each vertex will be in at most ~B~ pairs, this will take ~\mathcal{O}(N \times B)~ time. Here, it is optimal to choose ~B = \sqrt N~.

Time Complexity: ~\mathcal{O}(N \times (\log N + \sqrt N))~

Alternate Solution:

An alternative solution is to use centroid decomposition, DSU on a tree, or other small to large merging techniques. For each vertex, we will consider the path between pairs of vertices with that vertex as its lowest common ancestor (for some arbitrary rooting of the tree). We can perform a depth first search from the current vertex (ignoring excluded vertices in the case of centroid decomposition, and the heavy child in the case of DSU) and keep track of the shortest, and second shortest distance for each colour. The answer for each colour is the sum of the two shortest distances.

Time Complexity: ~\mathcal{O}(N \times \log N)~

Subtask 4

For the fourth subtask, we can use the same idea for the third subtask, and use the distance computation method for a cactus in the second subtask. The time complexity remains the same.

Time Complexity: ~\mathcal{O}(N \times (\log N + \sqrt N))~

Alternate Solution:

Similar to subtask 2, we will transform the cactus into a weighted tree. The alternate solution from subtask 3 can be used to compute the answer for each colour, however cycles will need to be handled separately. When a cycle is first encountered (first vertex in the cycle is a centroid for centroid decomposition, or first vertex in the pre-order traversal for DSU on a tree), we can treat the cycle as a line graph starting at the current vertex (by removing one of the two adjacent edges to the current vertex), and use the same depth first search technique in subtask 3 (ignoring the current vertex's non cycle children). Be sure to consider both line graphs that can be created from the cycle by removing an adjacent edge. The only cases that are not covered are paths that pass through the current vertex, however that will be covered by the solution from subtask 3. Be careful when using centroid decomposition, as the first vertex in a cycle encountered in a depth first search can change, as the root is not fixed.

Time Complexity: ~\mathcal{O}(N \times \log N)~