Limits: 1s, 256 MB
Safwan is the new governor of the country Homeland. Homeland is formed with set of N islands having N-1 bidirectional bridges among them forming the topology of a tree. Each bridge has unit length of 1 kilometer. Initially some island have small transportable lighthouse. These lighthouse can be lit if it has power supply in it. Power can be supplied directly from a generator located in the same island or any other lighthouse which already has power supply, via cable connection. You have infinite supply of 1 kilometer long cables. You cannot cut or merge any cable but make connection between two lighthouses in adjacent islands. Each island have different cost to install a generator. Now you want to install a generator on an island and powerup all the lighthouses. While moving an island can contain multiple lighthouse and/or a generator but after moving all lighthouses, an island can either contain a generator and a lighthouse or a single lighthouse. The cost of moving a lighthouse to any adjacent island is 1 unit. Now your task is to help Safwan finding the minimum cost.
This is a companion discussion topic for the original entry at https://toph.co/p/lighthouse