Hints: Building Tree

Look at one path in the original graph. If the path has length $k$, what does that say about edge weight $k$ on this path?

Answer to Hint 1: The path length is the MEX of the weights on the path, so weight $k$ is absent from the path.

Therefore, if two original vertices can be connected by a path that avoids all edges of weight $k$, then their distance is at most $k$.

Can we reverse the previous statement? If $\mathrm{dis}(u,v) = k$, what graph must still connect $u$ and $v$?

Answer to Hint 3: If there is a path from $u$ to $v$ with MEX $k$, then that path has no edge of weight $k$. So $u$ and $v$ are connected after deleting all edges of weight $k$.

This gives the key formula:

$$ \mathrm{dis}(u,v)=\min \{k : u \text{ and } v \text{ are connected after deleting all weight-}k\text{ edges}\}. $$

Why is it enough to consider only $k = 0, 1, \ldots, m$?

Answer to Hint 5: Every edge weight is between $0$ and $m$. Also, any path has at most $m$ edges, but there are $m+1$ possible weights, so the path misses at least one weight from $0$ to $m$.

Thus if two vertices are connected at all, their distance is some value in $[0,m]$.

Now forget the original graph for a moment. The new graph has $q$ vertices, and the cost between two new vertices is determined only by their colors. What standard graph problem are we solving on the colors?

Answer to Hint 7: We need a minimum spanning tree on the selected colors, where the edge cost between colors $a$ and $b$ is $\mathrm{dis}(a,b)$.

If the same color appears several times among the $c_i$, those new vertices can be connected to each other with cost $0$, so we only need to connect the distinct colors.

How can we run Kruskal without explicitly computing every pairwise $\mathrm{dis}$ first?

Answer to Hint 9: Process possible costs $k$ in increasing order. For a fixed $k$, build the connected components of the original graph after deleting all edges of weight $k$.

Inside one such component, every selected color can be connected to every other selected color with cost at most $k$. So in Kruskal, all current MST components represented inside this original component may be merged using edges of cost $k$.

For a slow but clear solution, what should we do for each $k$?

Answer to Hint 11: Rebuild a DSU on the original $n$ vertices using all edges whose weight is not $k$.

Then group the distinct selected colors by their DSU root. For every group, merge the corresponding color-components in the answer DSU, adding $k$ for each successful merge.

Why is it okay to merge a whole group by connecting everything to the first color in that group?

Answer to Hint 13: At the current cost $k$, all colors in the same original DSU component form a clique of available edges of cost at most $k$.

Kruskal only needs enough edges to merge the currently different answer components in that clique. A star from one representative color is enough to merge them all, and each successful DSU union contributes exactly one MST edge of cost $k$.

After processing all $k$, if the answer DSU has not connected all distinct colors, output $-1$. Otherwise, the accumulated sum is the minimum total time.

The official optimized solution keeps the same Kruskal idea, but avoids rebuilding DSU for every $k$ by using divide-and-conquer over weights together with rollback DSU.