First, take the whole tree A as B. For this, cost would be minimum weight among terminals
* n - 1
. Let's name this minimum weighted terminal as node K
.
As you can see, among all the possibility of tree B where K must be included, this is the maximum cost. Also notice, this is the maximum cost where n - 1
edges are present.
But this is not the final maximum cost. You still have to head toward max cost.
So where can we go from this state? Let's move forward by removing only one node/edge.
Which node can I remove safely? Node K. Because I already know the max cost where node K must exist. We don't need this anymore.
Remove node K. Then apply the same process for the produced tree. By induction, you can see that answer would be
for i = 1 to n - 1
ans = max(ans, min_weight_in_this_tree * currentEdge)
remove minimum weighted node