Minimum number of leaves required to be removed from a Tree to satisfy the given condition | Java 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
import java . util . * ; class GFG { static int cnt = 0 ; static void dfs ( int [ ] val , int [ ] cost , Vector < Integer > [ ] 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 ] . get ( i ) , s ) ; } } public static void main ( String [ ] args ) { 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 } ; @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] tr = new Vector [ n + 1 ] ; for ( int i = 0 ; i < tr . length ; i ++ ) tr [ i ] = new Vector < Integer > ( ) ; tr [ 0 ] . add ( 3 ) ; tr [ 0 ] . add ( 4 ) ; tr [ 4 ] . add ( 6 ) ; tr [ 6 ] . add ( 2 ) ; tr [ 2 ] . add ( 1 ) ; tr [ 2 ] . add ( 8 ) ; tr [ 8 ] . add ( 5 ) ; tr [ 5 ] . add ( 7 ) ; dfs ( val , cost , tr , 0 , 0 ) ; System . out . print ( n - cnt ) ; } }