Gotham is being terrorized by joker, specially in night. batman has to stop him, but he can only do so if he catches joker on a well-lit street. gotham has n junctions fully-connected by m streets, but batman only has n − 1 street lights. lights are placed on streets, and a street with a light is considered well-lit. at most one light can be placed on each street.

(a) let l(e) denote the length of road e. batman senses that joker is more likely to end up on longer roads, so he wants to prioritize lighting longer roads. additionally, he wants to make sure that there is a well-lit path (a sequence of connected well-lit edges) from every junction to every other junction to make sure that all of gotham is covered. design an efficient algorithm for batman to choose which roads to light, maximizing the total length of well-lit roads under the above constraint.

(b) batman showed your algorithm to alfred, and alfred said, "know your algorithms, master wayne. this doesn’t have proof of correctness." address the concern raised by alfred.

(c) call the lit-up road network obtained in part (a) dkn (dark knight network). one of gotham’s roads e 0 has now been placed under maintenance, increasing the length of that road — the length of other roads e 6= e 0 remains the same. should batman update the placement of the n−1 street lights for his dkn? if ‘no’, justify your answer, otherwise design an efficient algorithm to compute an updated placement incorporating the road length increase