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
function addEdge ( adj , u , v ) { adj [ u ] . push ( v ) ; adj [ v ] . push ( u ) ; } function printGraph ( adj , V ) { for ( var v = 0 ; v < V ; ++ v ) { document . write ( " " + v + " " ) ; for ( var x of adj [ v ] ) document . write ( " " + x ) ; document . write ( " " ) ; } } function findMinOperationUtil ( dp , adj , A , src , parent ) { dp [ src ] [ 0 ] = dp [ src ] [ 1 ] = 0 ; for ( var V of adj [ src ] ) { if ( V == parent ) continue ; findMinOperationUtil ( dp , adj , A , V , src ) ; dp [ src ] [ 0 ] = Math . max ( dp [ src ] [ 0 ] , dp [ V ] [ 0 ] ) ; dp [ src ] [ 1 ] = Math . max ( dp [ src ] [ 1 ] , dp [ V ] [ 1 ] ) ; } A [ src - 1 ] += dp [ src ] [ 0 ] - dp [ src ] [ 1 ] ; if ( A [ src - 1 ] > 0 ) { dp [ src ] [ 1 ] += A [ src - 1 ] ; } else { dp [ src ] [ 0 ] += Math . abs ( A [ src - 1 ] ) ; } } function findMinOperation ( adj , A , V ) { var dp = Array . from ( Array ( V + 1 ) , ( ) => Array ( 2 ) . fill ( 0 ) ) ; findMinOperationUtil ( dp , adj , A , 1 , 0 ) ; var minOperations = dp [ 1 ] [ 0 ] + dp [ 1 ] [ 1 ] ; return minOperations ; } var V = 5 ; var adj = Array . from ( Array ( V + 1 ) , ( ) => Array ( ) ) ; addEdge ( adj , 1 , 2 ) ; addEdge ( adj , 1 , 3 ) ; var A = [ 1 , - 1 , 1 ] ; var minOperations = findMinOperation ( adj , A , V ) ; document . write ( minOperations ) ;