Editorial: Building Tree

We are given an original weighted undirected graph on $n$ vertices. A path does not have the usual sum of edge weights. Instead, if the set of weights appearing on the path is $S$, the path length is $\operatorname{mex}(S)$.

Then we are given $q$ vertices in a new graph. Vertex $i$ has color $c_i$, which is a vertex of the original graph. We may add an edge between new vertices $i$ and $j$ with cost $\mathrm{dis}(c_i,c_j)$, where $\mathrm{dis}$ is the minimum MEX-path length in the original graph. We need the minimum cost to make the new graph connected.

This editorial focuses on a slow but conceptually direct solution. The final official solution optimizes exactly the same idea.

Fix two original vertices $u$ and $v$.

Suppose there is a path from $u$ to $v$ whose MEX is $k$. By the definition of MEX:

• all weights $0,1,\ldots,k-1$ appear on the path;
• weight $k$ does not appear on the path.

For minimizing the MEX, the important part is the second bullet. If a path avoids weight $k$, then its MEX is at most $k$, because $k$ is one of the missing weights.

So, if $u$ and $v$ are connected after deleting all weight-$k$ edges, then:

The reverse direction is also enough for an exact formula. If the best path has MEX $d$, then that path avoids weight $d$, so $u$ and $v$ are connected after deleting weight $d$.

Therefore:

The values of $k$ we need to test are only $0,1,\ldots,m$, because all edge weights lie in that range.

The new graph can add an edge between any two new vertices whose colors are connected in the original graph. The edge cost depends only on their colors:

So this is just a minimum spanning tree problem on the new vertices with these pairwise costs.

There is one small simplification. If the same original color appears multiple times among the $c_i$, those new vertices can be connected together with cost $0$, using the empty path from a vertex to itself. So we only need to connect the distinct colors that appear in the list.

Let these distinct colors be $a_0,a_1,\ldots,a_{s-1}$. We need the MST of the complete graph on these $s$ colors, where the edge between $a_i$ and $a_j$ has weight $\mathrm{dis}(a_i,a_j)$.

As a subtask, suppose $s$ is small enough that we can explicitly compute the distance between every pair of selected colors.

From Subtask 1, for any two original vertices $u$ and $v$:

So we can compute all pairwise MEX distances by testing each possible missing weight $k$.

For a fixed $k$, build a DSU on the original graph using every edge whose weight is not $k$. Then all vertices in the same DSU component have MEX-distance at most $k$, because there is a path between them that avoids weight $k$.

Now look only at the selected colors $a_0,a_1,\ldots,a_{s-1}$. If two selected colors are in the same DSU component for this $k$, and their pairwise distance has not been assigned yet, then their distance is exactly $k$. It cannot be smaller, because we process $k$ in increasing order.

The slow subtask algorithm is:

1. Initialize every pair distance as unknown.
2. For $k=0,1,\ldots,m$, rebuild the DSU using all edges with weight different from $k$.
3. Group selected colors by their DSU root.
4. Inside each group, assign distance $k$ to every still-unknown pair.

After this, we have the complete graph on selected colors explicitly: the edge between $a_i$ and $a_j$ has weight equal to the first $k$ for which they appeared in the same deleted-weight component.

This is too slow for the full constraints, since a large component may contain many selected colors and create many pairs. But it is a useful subtask because it makes the meaning of the pairwise MEX costs completely concrete.

The most literal implementation is:

1. For every pair of distinct selected colors $(a_i,a_j)$, compute $\mathrm{dis}(a_i,a_j)$.
2. Run Kruskal on all those pairwise edges.

To compute one distance, try every $k$ from $0$ to $m$:

1. Build a DSU using all original edges whose weight is not $k$.
2. If $a_i$ and $a_j$ are in the same DSU component, then $\mathrm{dis}(a_i,a_j)=k$ and we can stop.

This is the easiest possible way to see the idea, but it is extremely slow. It rebuilds the original graph connectivity for every pair and every possible deleted weight.

We can keep the same logic but organize it like Kruskal.

Kruskal processes edges by increasing weight. Here, if two selected colors are connected after deleting weight $k$, then Kruskal has an available edge between them with cost at most $k$. The first value of $k$ where this happens is exactly their distance.

So for each $k=0,1,\ldots,m$:

1. Rebuild a DSU on the original graph using all edges with weight not equal to $k$.
2. Look at each distinct selected color and find its original DSU root.
3. Colors with the same root form a clique of available edges of cost at most $k$.
4. In the MST DSU over selected colors, merge all currently different components inside each such clique, adding $k$ for every successful merge.

This is exactly Kruskal, but we never need to create all $s(s-1)/2$ edges explicitly.

Suppose for the current $k$, selected colors

are in the same component of the original graph after deleting weight $k$.

Then every pair among them has an available edge with cost at most $k$. At this Kruskal stage, we only care about merging different MST components. Connecting all of them to $x_1$ is enough:

• if $x_i$ is already in the same MST component as $x_1$, the union does nothing;
• otherwise, we add one edge of cost $k$ and merge one MST component.

This produces the same effect as considering all clique edges of this cost.

The slow version still rebuilds the graph DSU from scratch for every deleted weight $k$. The official solution speeds up exactly this part.

For a fixed $k$, we need connectivity in the graph containing all edges whose weight is not $k$. Equivalently, when checking a range of possible missing weights, it is useful to maintain the graph made of edges whose weights are outside that range.

The divide-and-conquer state is:

where the rollback DSU on original vertices currently contains all edges with weights outside the interval $[l,r)$.

At the root, we call $\mathrm{Solve}(0,m+1)$. There are no weights outside $[0,m+1)$, so the DSU starts empty.

Now split the interval at

To recurse into $[l,\mathrm{mid})$, the DSU should contain all edges with weights outside $[l,\mathrm{mid})$.

It already contains all edges outside $[l,r)$. So we only need to temporarily add edges with weights in $[\mathrm{mid},r)$.

After adding them, any path inside this DSU avoids every weight in $[l,\mathrm{mid})$. In particular, it avoids weight $l$. Therefore any two selected colors that become connected now have distance at most $l$.

Because all smaller costs were handled before reaching this range, Kruskal may charge such a merge with cost $l$.

Then we recurse into $\mathrm{Solve}(l,\mathrm{mid})$ and roll back the temporary edges.

Similarly, to recurse into $[\mathrm{mid},r)$, we temporarily add edges with weights in $[l,\mathrm{mid})$.

Now the DSU contains all edges outside $[\mathrm{mid},r)$. Any path inside it avoids every weight in $[\mathrm{mid},r)$, so it avoids weight $\mathrm{mid}$.

Thus any newly connected selected-color components can be merged in Kruskal with cost $\mathrm{mid}$.

Then we recurse into $\mathrm{Solve}(\mathrm{mid},r)$ and roll back.

The same DSU is shared by many recursive calls. Before adding temporary edges for one branch, we remember the current rollback stack size. After finishing that branch, we undo all DSU changes back to that saved size.

This lets each edge be added in $O(\log m)$ recursive levels overall, instead of rebuilding connectivity from scratch for every $k$.

The official code keeps two DSUs:

• d_v: rollback DSU over the original graph vertices;
• d_c: normal DSU over the distinct selected colors, used for the MST/Kruskal process.

Each component of d_v stores idx, one selected color currently inside that component, or $-1$ if the component has none.

When d_v is about to unite two original-graph components:

1. If both components contain selected colors, their representatives in d_c now have an available edge at the current divide-and-conquer boundary cost.
2. If d_c.unite(...) succeeds, we add that boundary cost to the answer.
3. Then the original components are united in d_v, and the merged component keeps one selected representative.

Why is one representative enough? Inside a d_v component, all selected colors that have already met there are connected in d_c. So for future merges, the whole group can be represented by any one of them.

The core recursion is:

Solve(l, r):
    if r - l == 1:
        return

    mid = (l + r) / 2

    save rollback state
    add all edges with weights in [mid, r), charging successful color merges by l
    Solve(l, mid)
    rollback

    save rollback state
    add all edges with weights in [l, mid), charging successful color merges by mid
    Solve(mid, r)
    rollback

This is the same Kruskal process as Subtask 5, but batched by weight ranges instead of rebuilding a DSU for every single missing weight.

For original vertices $u$ and $v$,

Proof.

If $u$ and $v$ are connected after deleting all weight-$k$ edges, there is a path from $u$ to $v$ that does not contain weight $k$. Therefore the MEX of this path is at most $k$, so $\mathrm{dis}(u,v)\le k$.

Conversely, if there is a path from $u$ to $v$ with MEX $k$, then weight $k$ is absent from that path. Thus the same path still exists after deleting all weight-$k$ edges, so $u$ and $v$ are connected in that deleted graph.

Taking the minimum possible $k$ proves the lemma.

For a fixed $k$, every group of selected colors lying in the same component after deleting weight $k$ can be treated as a clique of edges of cost at most $k$.

Proof.

Any two colors in the group are connected after deleting weight $k$. By Lemma 1, their distance is at most $k$. Therefore the complete graph on selected colors has an edge of weight at most $k$ between every pair in the group.

Processing $k$ from $0$ to $m$ and merging selected-color components inside every group is equivalent to Kruskal’s algorithm.

Proof.

By Lemma 1, an edge between two selected colors has MST weight $d$ exactly when $d$ is the first deleted-weight value that connects them.

When our algorithm is at value $k$, all edges whose first successful deleted-weight value is at most $k$ have become available. Inside each group from the deleted-weight graph, Lemma 2 says the relevant selected colors form a clique of edges with cost at most $k$. Merging all current MST components inside that clique is exactly what Kruskal would do after seeing enough edges from the clique.

The DSU prevents cycles. If a merge is still successful at value $k$, then these two MST components were not connected by any earlier processed edge, so charging this merge at the current Kruskal level is valid. Thus the algorithm performs Kruskal’s choices in nondecreasing edge weight order.

The divide-and-conquer rollback DSU performs the same Kruskal merges as the slow algorithm, but batches many values of $k$ together.

Proof.

Consider a call $\mathrm{Solve}(l,r)$. By construction, the rollback DSU contains all edges whose weights are outside $[l,r)$.

For the left child $[l,\mathrm{mid})$, we add all weights in $[\mathrm{mid},r)$, so the DSU now contains all edges outside $[l,\mathrm{mid})$. Therefore, any selected-color components that become connected at this moment have an available edge of cost at most $l$.

For the right child $[\mathrm{mid},r)$, we add all weights in $[l,\mathrm{mid})$, so the DSU contains all edges outside $[\mathrm{mid},r)$. Any selected-color components that become connected at this moment have an available edge of cost at most $\mathrm{mid}$.

The recursion visits the left half before the right half, so these boundary costs are considered in increasing order. The selected-color DSU d_c ignores merges that were already achieved by smaller costs, exactly like Kruskal. Thus the batched recursion has the same effect as processing all deleted weights one by one.

If the algorithm connects all distinct selected colors, the accumulated value is the minimum time needed to connect the new graph. If it does not connect them, the answer is $-1$.

Proof.

By Subtask 2, the problem is the MST problem on distinct selected colors with edge weights $\mathrm{dis}$. Lemma 3 shows that the one-by-one algorithm is Kruskal’s algorithm on exactly that graph, and Lemma 4 shows that the divide-and-conquer rollback DSU performs the same Kruskal merges. Kruskal returns a minimum spanning tree when one exists.

If the selected colors remain disconnected after all $k$, then no available edges can connect all of them, so no connected new graph can be built.

Let $s$ be the number of distinct colors in the query list.

For every $k=0,1,\ldots,m$, the slow implementation from Subtask 5:

• rebuilds a DSU from $m$ edges;
• groups the $s$ selected colors by their DSU root;
• performs some DSU unions on the selected-color MST DSU.

The complexity is roughly

This is far too slow for the full constraints, but it is much easier to understand than the official optimized solution.

For the divide-and-conquer version, each original edge is temporarily inserted into the rollback DSU on $O(\log m)$ recursion levels. A rollback DSU uses union by size but no path compression, so each find costs $O(\log n)$.

So the optimized solution runs in about

per test case, up to lower-order DSU work on the selected colors.

The important point is that the optimization does not compute all pairwise distances. It only discovers enough available edges, in Kruskal order, to build the MST over selected colors.