Given a tree with 'n' nodes and 'n-1' edges.
We are also given a set of 'n-1' weights .
We have to assign each weight to exactly one of the edges.
We have to assign it in a way such that the sum of all nodes in a tree is minimized.
Value of a node = maximum weight of all of its adjacent edges.
Example:- Edges:- (1--2), (2--3)
Weights:-{1,2}
Solution : — Assigning weight '2' to edge '1--2' and weight '1' to edge '2--3' , we get,
value of node '1' : — 2
value of node '2' : — 2
value of node '3' : — 1
Total minimum sum possible : — (2+2+1)=5 .
How to approach ?
Maybe a greedy approach works? Always put the minimum weighted edge on the edge that connects to the leaf node so the leaf node will have this value. Once you've done that to some leaf, remove it from the tree (aka just decrease the degree of his parent), so now either his parent becomes a new leaf or he doesnt. Repeat until all edges are exhausted.
Let me know if this does not work.