Блог пользователя MOOONI

Автор MOOONI, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • -22
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)