Count of Root to Leaf Paths consisting of at most M consecutive Nodes having value K | Initialize the adjacency list and visited array ; Function to find the number of root to leaf paths that contain atmost m consecutive nodes with value k ; Mark the current node as visited ; If value at current node is k ; Increment counter ; If count is greater than m return from that path ; Path is allowed if size of present node becomes 0 i . e it has no child root and no more than m consecutive 1 's ; Driver code ; Desigining the tree ; Counter counts no . of consecutive nodes
adj = [ [ ] for i in range ( 100005 ) ] NEW_LINE visited = [ 0 for i in range ( 100005 ) ] NEW_LINE ans = 0 ; NEW_LINE def dfs ( node , count , m , arr , k ) : NEW_LINE INDENT global ans NEW_LINE visited [ node ] = 1 ; NEW_LINE if ( arr [ node - 1 ] == k ) : NEW_LINE INDENT count += 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT count = 0 ; NEW_LINE DEDENT if ( count > m ) : NEW_LINE INDENT return ; NEW_LINE DEDENT if ( len ( adj [ node ] ) == 1 and node != 1 ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT for x in adj [ node ] : NEW_LINE INDENT if ( not visited [ x ] ) : NEW_LINE INDENT dfs ( x , count , m , arr , k ) ; NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 1 , 3 , 2 , 1 , 2 , 1 ] NEW_LINE N = 7 NEW_LINE K = 2 NEW_LINE M = 2 NEW_LINE adj [ 1 ] . append ( 2 ) ; NEW_LINE adj [ 2 ] . append ( 1 ) ; NEW_LINE adj [ 1 ] . append ( 3 ) ; NEW_LINE adj [ 3 ] . append ( 1 ) ; NEW_LINE adj [ 2 ] . append ( 4 ) ; NEW_LINE adj [ 4 ] . append ( 2 ) ; NEW_LINE adj [ 2 ] . append ( 5 ) ; NEW_LINE adj [ 5 ] . append ( 2 ) ; NEW_LINE adj [ 3 ] . append ( 6 ) ; NEW_LINE adj [ 6 ] . append ( 3 ) ; NEW_LINE adj [ 3 ] . append ( 7 ) ; NEW_LINE adj [ 7 ] . append ( 3 ) ; NEW_LINE counter = 0 ; NEW_LINE dfs ( 1 , counter , M , arr , K ) ; NEW_LINE print ( ans ) NEW_LINE DEDENT