Minimum number of leaves required to be removed from a Tree to satisfy the given condition | C ++ Program to find the minimum number of leaves to be deleted ; Stores the count of safe nodes ; Function to perform DFS on the Tree to obtain the count of vertices that are not required to be deleted ; Update cost to reach the vertex ; If the vertex does not satisfy the condition ; Otherwise ; Traverse its subtree ; Driver Code ; Stores the Tree ; Perform DFS ; Print the number of nodes to be deleted
#include <bits/stdc++.h> NEW_LINE using namespace std ; int cnt = 0 ; void dfs ( int * val , int * cost , vector < vector < int > > & tr , int u , int s ) { s = s + cost [ u ] ; if ( s < 0 ) s = 0 ; if ( s > val [ u ] ) return ; cnt ++ ; for ( int i = 0 ; i < tr [ u ] . size ( ) ; i ++ ) { dfs ( val , cost , tr , tr [ u ] [ i ] , s ) ; } } int main ( ) { int n = 9 ; int val [ ] = { 88 , 22 , 83 , 14 , 95 , 91 , 98 , 53 , 11 } ; int cost [ ] = { -1 , 24 , -8 , 67 , 64 , 65 , 12 , -80 , 8 } ; vector < vector < int > > tr ( n + 1 ) ; tr [ 0 ] . push_back ( 3 ) ; tr [ 0 ] . push_back ( 4 ) ; tr [ 4 ] . push_back ( 6 ) ; tr [ 6 ] . push_back ( 2 ) ; tr [ 2 ] . push_back ( 1 ) ; tr [ 2 ] . push_back ( 8 ) ; tr [ 8 ] . push_back ( 5 ) ; tr [ 5 ] . push_back ( 7 ) ; dfs ( val , cost , tr , 0 , 0 ) ; cout << n - cnt ; return 0 ; }