W--o_o--W's blog

By W--o_o--W, history, 12 months ago, In English,


I came up with the following problem but I'm not sure if it is possible to solve it in less than O(n2), any ideas?

You are given a weighted tree with n nodes and you are allowed to swap the costs (1 ≤ cost ≤ n) of two edges at most once such that the sum of all paths in the tree is maximum.

Read more »

  • Vote: I like it
  • +52
  • Vote: I do not like it