Hello,

I came up with the following problem but I'm not sure if it is possible to solve it in less than *O*(*n*^{2}), 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.