human
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"
Solution in Python:
assistant
#Here is code to minimum Operations to make value of all vertices of the tree Zero and the other steps required.
 def addEdge ( adj , u , v ) :
	adj [ u ] . append ( v )
	adj [ v ] . append ( u )
def printGraph ( adj , V ) :
	for v in range ( 0 , V ) :
		print ( " Adjacency ▁ list ▁ of ▁ vertex " , v )
		print ( " head " , end = " ▁ " )
		for x in adj [ v ] :
			print ( " - > " , x , end = " " )
		print ( )
def findMinOperationUtil ( dp , adj , A , src , parent ) :
	dp [ src ] [ 0 ] = dp [ src ] [ 1 ] = 0
	for V in adj [ src ] :
		if V == parent :
			continue
		findMinOperationUtil ( dp , adj , A , V , src )
		dp [ src ] [ 0 ] = max ( dp [ src ] [ 0 ] , dp [ V ] [ 0 ] )
		dp [ src ] [ 1 ] = 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 ] += abs ( A [ src - 1 ] )
def findMinOperation ( adj , A , V ) :
	dp = [ [ 0 , 0 ] for i in range ( V + 1 ) ]
	findMinOperationUtil ( dp , adj , A , 1 , 0 )
	minOperations = dp [ 1 ] [ 0 ] + dp [ 1 ] [ 1 ]
	return minOperations
if __name__ == " _ _ main _ _ " :
	V = 5
	adj = [ [ ] for i in range ( V + 1 ) ]
	addEdge ( adj , 1 , 2 )
	addEdge ( adj , 1 , 3 )
	A = [ 1 , - 1 , 1 ]
	minOperations = findMinOperation ( adj , A , V )
	print ( minOperations )