For up to $11$ of the original $15$ available marks, we note that $D=0$. We can first sort all edges by weight, breaking ties by taking the edge which appeared earlier in the input. We then run a standard MST algorithm, keeping track of the number of new edges in the MST.

Time Complexity: $\mathcal{O}(M\log M)$

Full Solution

For the full solution, we have to account for when $D\ne 0$.

There are two solutions to do this.

Solution 1

To find the best value, we take the total of the MST from before and subtract at most $D$ from the largest edge. Store this value in some variable for now.

Next, we try to see if we can reduce the number of days required by $1$. To do this, we take each unused original edge and try to use it to replace a new edge in the MST. To find the largest value to remove, we use a sparse table to find the largest value in $\mathcal{O}(\log N)$ time. The new cost will be old MST cost + new edge - removed edge - min*(D, largest remaining edge). If this equals the best value we can get in the old edge, we reduce the days required by 1 and stop trying.

Solution 2

First, we generate an MST similarly to what we did for the first $11$ points. However, we notice that only edges with weight equal to that of the heaviest edge will be replaced. Let us call this weight $w_l$.

Then, we run Kruskal's algorithm, with a slight modification: if the edge's weight is less than $w_l$ or was in the original MST and has a weight equal to $w_l$, then we add it into the MST like in the standard algorithm. However, if the weight of the edge is $\le D$ and is also an old edge, then it can replace one of the edges we used, thus decreasing the number of days required by $1$.

Time Complexity: $\mathcal{O}(M\log M)$