Let's consider a tree with root $r$ ( not necessary binary) and to each node $i$ we associate a cost $\sigma(i)$ that can be negative, positive or zero. We want to select the set of nodes that minimize $\sum_i \sigma(i)$. Of course, the problem until now is easy :
If there are only non-negative costs the solution is the empty set.
If there are some non-positive costs, we select them all.
But, there is an additional constraint that states: "if a node $\sigma(i)$ is selected, its predecessor to the root is also selected. Thus we are looking for the set of nodes that grow upward to the root and that minimize that sum, or equivalently, we are looking at a subtree of root $r$ that minimize that sum.
My question is how to design an algorithm that solves this problem and how to prove its correctness and compute its complexity?
(I have a hint that states that we could do some bottom-up traversal, of the tree but I don't know how to use this information)
Any help will be appreciated. Thanks