Albero di spanning minimo con un limite di bordo particolare (continua)

Question

Ho recentemente riscontrato un problema di codifica, in particolare il Problema CCC S4.

Nel problema, afferma che ti viene dato un albero che sparnisce, o in altro modo un "piano valido di tubi", che si collegano ogni casa l'uno all'altro. Tuttavia, l'albero non è l'albero di spanning minimo. Puoi usare un potenziatore, in parole esatte, con potenza D, per ridurre il peso di un bordo a quello che è max (0, peso-d). Hai un certo numero di giorni per rendere l'albero spanning dato un albero minimo. In questi giorni, è possibile disattivare qualsiasi bordo dell'albero che si spinse e attivare un altro vantaggio di tua scelta. Non importa se l'albero non è un albero che sparnisce nel processo, tuttavia, alla fine, dovrebbe essere. Vuoi anche ridurre al minimo la quantità di giorni necessari per farlo.

Ho lottato con il problema per molto tempo e non riesco a trovare alcuna soluzione. Sono in grado di trovare l'albero minimo, ma sto lottando con l'implementazione del potenziatore.

Apprezzerei qualsiasi aiuto per il mio problema e i codici di esempio saranno ancora migliori.

Ho fatto anche una domanda simile qui:Albero di spanning minimo in modo tale che un bordo possa essere ridotto al minimo