Hi guys! Here’s a problem I’m the author of it (and I don’t know the solution!) You are given a weighted tree with n nodes such that the weight of the ith node is w[i]. In each step you will do the following : Chose 2 adjacent nodes with weights V1 and V2. Delete the edge between them and put one of them on the other. Then the weight of the new node will be V1 + V2 and the cost of this action will be V1 + V2 as well. Now you are supposed to have a node with 0 adjacent nodes. What is the minimum cost of it?
So if you were given a tree with 2 nodes with weights 5 and 7 then the minimum cost would be 12.
I’ve not set any constraints yet but do your best on it! O(n * n) is preferred ...
I use google translator from Russian
I feel it like this: it is enough to take an edge so that the sum of the vertices falling into the edge is minimal. For a particular tree, this step can be performed in O (n) by a simple enumeration, and when an edge is selected, it can also be combined into O (n). There are n such steps; therefore, the complexity is O (n ^ 2)