Minimum number of leaves required to be removed from a Tree to satisfy the given condition | 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
var cnt = 0 ; function dfs ( val , cost , tr , u , s ) { s = s + cost [ u ] ; if ( s < 0 ) s = 0 ; if ( s > val [ u ] ) return ; cnt ++ ; for ( var i = 0 ; i < tr [ u ] . length ; i ++ ) { dfs ( val , cost , tr , tr [ u ] [ i ] , s ) ; } } var n = 9 ; var val = [ 88 , 22 , 83 , 14 , 95 , 91 , 98 , 53 , 11 ] ; var cost = [ - 1 , 24 , - 8 , 67 , 64 , 65 , 12 , - 80 , 8 ] ; var tr = Array . from ( Array ( n + 1 ) , ( ) => Array ( ) ) ; tr [ 0 ] . push ( 3 ) ; tr [ 0 ] . push ( 4 ) ; tr [ 4 ] . push ( 6 ) ; tr [ 6 ] . push ( 2 ) ; tr [ 2 ] . push ( 1 ) ; tr [ 2 ] . push ( 8 ) ; tr [ 8 ] . push ( 5 ) ; tr [ 5 ] . push ( 7 ) ; dfs ( val , cost , tr , 0 , 0 ) ; document . write ( n - cnt ) ;