Subtree with minimum sum of nodes' costs 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
For a node $i$ with children $j_1,\ldots,j_d$, let us denote the best solution for the subtree rooted at $i$ by $\tau(i)$; you're interested in $\tau(r)$, where $r$ is the root. The function $\tau$ satisfies the recurrence
$$
\tau(i) = \min(0,  \sigma(i) + \tau(j_1) + \cdots + \tau(j_d)).
$$
Indeed, there are two cases to consider. Either we take no vertex, in which the answer is 0. Otherwise, we must take $i$ itself (by the constraint), and then we should take the best solutions for the subtrees rooted at all children of $i$.

Like all such recurrences on trees, this one can be evaluated in linear time in many ways.