A new problem

Правка en1, от MOOONI, 2020-03-08 07:50:14

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 ...

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский MOOONI 2020-03-08 07:50:14 713 Initial revision (published)