Minimum Operations to make value of all vertices of the tree Zero | A utility function to add an edge in an undirected graph ; A utility function to print the adjacency list representation of graph ; Utility Function for findMinOperation ( ) ; Base Case for current node ; Iterate over the adjacency list for src ; calculate DP table for each child V ; Number of Increase Type operations for node src is equal to maximum of number of increase operations required by each of its child ; Number of Decrease Type operations for node src is equal to maximum of number of decrease operations required by each of its child ; After performing operations for subtree rooted at src A [ src ] changes by the net difference of increase and decrease type operations ; for negative value of node src ; Returns the minimum operations required to make value of all vertices equal to zero , uses findMinOperationUtil ( ) ; Initialise DP table ; find dp [ 1 ] [ 0 ] and dp [ 1 ] [ 1 ] ; Driver code ; Build the Graph / Tree
def addEdge ( adj , u , v ) : NEW_LINE INDENT adj [ u ] . append ( v ) NEW_LINE adj [ v ] . append ( u ) NEW_LINE DEDENT def printGraph ( adj , V ) : NEW_LINE INDENT for v in range ( 0 , V ) : NEW_LINE INDENT print ( " Adjacency ▁ list ▁ of ▁ vertex " , v ) NEW_LINE print ( " head " , end = " ▁ " ) NEW_LINE for x in adj [ v ] : NEW_LINE INDENT print ( " - > " , x , end = " " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT DEDENT def findMinOperationUtil ( dp , adj , A , src , parent ) : NEW_LINE INDENT dp [ src ] [ 0 ] = dp [ src ] [ 1 ] = 0 NEW_LINE for V in adj [ src ] : NEW_LINE INDENT if V == parent : NEW_LINE INDENT continue NEW_LINE DEDENT findMinOperationUtil ( dp , adj , A , V , src ) NEW_LINE dp [ src ] [ 0 ] = max ( dp [ src ] [ 0 ] , dp [ V ] [ 0 ] ) NEW_LINE dp [ src ] [ 1 ] = max ( dp [ src ] [ 1 ] , dp [ V ] [ 1 ] ) NEW_LINE DEDENT A [ src - 1 ] += dp [ src ] [ 0 ] - dp [ src ] [ 1 ] NEW_LINE if A [ src - 1 ] > 0 : NEW_LINE INDENT dp [ src ] [ 1 ] += A [ src - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ src ] [ 0 ] += abs ( A [ src - 1 ] ) NEW_LINE DEDENT DEDENT def findMinOperation ( adj , A , V ) : NEW_LINE INDENT dp = [ [ 0 , 0 ] for i in range ( V + 1 ) ] NEW_LINE findMinOperationUtil ( dp , adj , A , 1 , 0 ) NEW_LINE minOperations = dp [ 1 ] [ 0 ] + dp [ 1 ] [ 1 ] NEW_LINE return minOperations NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT V = 5 NEW_LINE adj = [ [ ] for i in range ( V + 1 ) ] NEW_LINE addEdge ( adj , 1 , 2 ) NEW_LINE addEdge ( adj , 1 , 3 ) NEW_LINE A = [ 1 , - 1 , 1 ] NEW_LINE minOperations = findMinOperation ( adj , A , V ) NEW_LINE print ( minOperations ) NEW_LINE DEDENT