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
cnt = 0 NEW_LINE def dfs ( val , cost , tr , u , s ) : NEW_LINE INDENT global cnt NEW_LINE s = s + cost [ u ] NEW_LINE if ( s < 0 ) : NEW_LINE INDENT s = 0 NEW_LINE DEDENT if ( s > val [ u ] ) : NEW_LINE INDENT return NEW_LINE DEDENT cnt += 1 NEW_LINE for i in range ( 0 , len ( tr [ u ] ) ) : NEW_LINE INDENT dfs ( val , cost , tr , tr [ u ] [ i ] , s ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 9 NEW_LINE val = [ 88 , 22 , 83 , 14 , 95 , 91 , 98 , 53 , 11 ] NEW_LINE cost = [ - 1 , 24 , - 8 , 67 , 64 , 65 , 12 , - 80 , 8 ] NEW_LINE tr = [ [ ] for i in range ( n + 1 ) ] NEW_LINE tr [ 0 ] . append ( 3 ) NEW_LINE tr [ 0 ] . append ( 4 ) NEW_LINE tr [ 4 ] . append ( 6 ) NEW_LINE tr [ 6 ] . append ( 2 ) NEW_LINE tr [ 2 ] . append ( 1 ) NEW_LINE tr [ 2 ] . append ( 8 ) NEW_LINE tr [ 8 ] . append ( 5 ) NEW_LINE tr [ 5 ] . append ( 7 ) NEW_LINE dfs ( val , cost , tr , 0 , 0 ) NEW_LINE print ( n - cnt ) NEW_LINE DEDENT