Count the nodes in the given tree whose weight is a powerful number | Python3 implementation to Count the Nodes in the given tree whose weight is a powerful number ; Function to check if the number is powerful ; First divide the number repeatedly by 2 ; Check if only 2 ^ 1 divides n , then return False ; Check if n is not a power of 2 then this loop will execute ; Find highest power of " factor " that divides n ; Check if only factor ^ 1 divides n , then return False ; n must be 1 now if it is not a prime number . Since prime numbers are not powerful , we return False if n is not 1. ; Function to perform dfs ; Check if weight of the current Node is a powerful number ; Driver code ; Weights of the Node ; Edges of the tree
graph = [ [ ] for i in range ( 100 ) ] NEW_LINE weight = [ 0 ] * 100 NEW_LINE ans = 0 NEW_LINE def isPowerful ( n ) : NEW_LINE INDENT while ( n % 2 == 0 ) : NEW_LINE INDENT power = 0 ; NEW_LINE while ( n % 2 == 0 ) : NEW_LINE INDENT n /= 2 ; NEW_LINE power += 1 ; NEW_LINE DEDENT if ( power == 1 ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT DEDENT factor = 3 NEW_LINE while ( factor * factor <= n ) : NEW_LINE INDENT power = 0 ; NEW_LINE while ( n % factor == 0 ) : NEW_LINE INDENT n = n / factor ; NEW_LINE power += 1 ; NEW_LINE DEDENT if ( power == 1 ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT factor += 2 ; NEW_LINE DEDENT return ( n == 1 ) ; NEW_LINE DEDENT def dfs ( Node , parent ) : NEW_LINE INDENT global ans ; NEW_LINE if ( isPowerful ( weight [ Node ] ) ) : NEW_LINE INDENT ans += 1 ; NEW_LINE DEDENT for to in graph [ Node ] : NEW_LINE INDENT if ( to == parent ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT dfs ( to , Node ) ; NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT weight [ 1 ] = 5 ; NEW_LINE weight [ 2 ] = 10 ; NEW_LINE weight [ 3 ] = 11 ; NEW_LINE weight [ 4 ] = 8 ; NEW_LINE weight [ 5 ] = 6 ; NEW_LINE graph [ 1 ] . append ( 2 ) ; NEW_LINE graph [ 2 ] . append ( 3 ) ; NEW_LINE graph [ 2 ] . append ( 4 ) ; NEW_LINE graph [ 1 ] . append ( 5 ) ; NEW_LINE dfs ( 1 , 1 ) ; NEW_LINE print ( ans ) ; NEW_LINE DEDENT