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 \neq 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)~