How to find a minimal rooted tree with maximial sum vertex weights? I have an undirected grid graph, nxm, where each vertex has a value (positive or negative) and I need to find the tree rooted at vertex (1,1) that maximizes the sum of these values with a minimal number vertices.
The tree do not have to go through all nodes, although the tree can pick a negative vertex so it can pick a positive one.
Edges have no value.
I will appreciate any advice.
 A: The optimal solution can be found as follows:  


*

*repeatedly delete from the vertices with negative weight the one, that has minimal weight and whose removal doesn't disconnect the graph, i.e. that isn't an articulation vertex.   

*replace each connected component of the subgraph induced by edges, that are ajacent to two vertices with positive weight, by a single vertex and assign to it the sum of all vertex weights in that component.  

*replace the paths between two vertices with positive weight by an edge, whose weight equals the sum of negative vertex weights on that path.  

*in the resulting tree-graph define the vertex that "contains" $(1,1)$ as the root  

*start a depth-first search from the root node: 


*

*after returning from descending into each of the children of a vertex $v$, either  


*

*add the sum of the weights $\omega(v)$ and $\omega(e)$ of $v$ and of the edge $e$ adjacent to $v$ and to $v$'s father-vertex $u$ if $\omega(v)+\omega(e)\gt 0$, i.e $\ \omega(u)=\omega(u)+\omega(e)+\omega(v)$ in that case 

*otherwise add nothing to the father-node weight and mark $e$ and $v$ as deleted   



*finally replace the tree-nodes and edges that aren't marked as deleted, by the corresponding vertices and edges of the original graph to obtain the optimal solution. 

