Minimum Operations to make value of all vertices of the tree Zero | CPP program to find the Minimum Operations to modify values of all tree vertices to 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void addEdge ( vector < int > adj [ ] , int u , int v ) { adj [ u ] . push_back ( v ) ; adj [ v ] . push_back ( u ) ; } void printGraph ( vector < int > adj [ ] , int V ) { for ( int v = 0 ; v < V ; ++ v ) { cout << " Adjacency list of vertex " << v < < " head " for ( auto x : adj [ v ] ) cout << " - > ▁ " << x ; printf ( " STRNEWLINE " ) ; } } void findMinOperationUtil ( int dp [ ] [ 2 ] , vector < int > adj [ ] , int A [ ] , int src , int parent ) { dp [ src ] [ 0 ] = dp [ src ] [ 1 ] = 0 ; for ( auto V : 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 ] ) ; } } int findMinOperation ( vector < int > adj [ ] , int A [ ] , int V ) { int dp [ V + 1 ] [ 2 ] ; memset ( dp , 0 , sizeof dp ) ; findMinOperationUtil ( dp , adj , A , 1 , 0 ) ; int minOperations = dp [ 1 ] [ 0 ] + dp [ 1 ] [ 1 ] ; return minOperations ; } int main ( ) { int V = 5 ; vector < int > adj [ V + 1 ] ; addEdge ( adj , 1 , 2 ) ; addEdge ( adj , 1 , 3 ) ; int A [ ] = { 1 , -1 , 1 } ; int minOperations = findMinOperation ( adj , A , V ) ; cout << minOperations ; return 0 ; }