Albero di spanning minimo in modo tale che un bordo possa essere ridotto al minimo

Question

Durante un esame di codifica del computer, ho riscontrato un tale problema.

Dato un elenco di vertici e bordi tra i vertici e un numero positivo, D, qual è l'albero di spanning minimo tra i vertici in modo tale che la somma delle lunghezze dei bordi sia minima, a condizione che sia possibile sottrarre qualsiasi bordo del tuo Scelta nell'albero con il numero positivo D e ridurre il peso di quel bordo a max (0, peso-d)?

So che l'algoritmo di Kruskal e Prim può essere tutti usati per risolvere la prima parte del problema, l'albero minimo di spanning e posso farlo. Tuttavia, ho lottato duramente per la seconda parte, poiché non so come ridurre al minimo il peso dell'albero dato il numero D.