Count of paths in given Binary Tree with odd bitwise AND for Q queries | Function to count number of paths in binary tree such that bitwise AND of all nodes is Odd ; vector dp to store the count of bitwise odd paths till that vertex ; Precomputing for each value ; Check for odd value ; Number of odd elements will be + 1 till the parent node ; For even case ; Since node is even Number of odd elements will be 0 ; Even value node will not contribute in answer hence dp [ i ] = previous answer ; Printing the answer for each query ; Vector to store queries
def compute ( query ) : NEW_LINE INDENT v = [ None ] * 100001 NEW_LINE dp = [ None ] * 100001 NEW_LINE v [ 1 ] = 1 NEW_LINE v [ 2 ] = 0 NEW_LINE dp [ 1 ] = 0 NEW_LINE dp [ 2 ] = 0 NEW_LINE for i in range ( 3 , 100001 ) : NEW_LINE INDENT if ( i % 2 != 0 ) : NEW_LINE INDENT if ( ( i // 2 ) % 2 == 0 ) : NEW_LINE INDENT v [ i ] = 1 NEW_LINE dp [ i ] = dp [ i - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT v [ i ] = v [ i // 2 ] + 1 NEW_LINE dp [ i ] = dp [ i - 1 ] + v [ i ] - 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT v [ i ] = 0 NEW_LINE dp [ i ] = dp [ i - 1 ] NEW_LINE DEDENT DEDENT for x in query : NEW_LINE INDENT print ( dp [ x ] ) NEW_LINE DEDENT DEDENT query = [ 5 , 2 ] NEW_LINE compute ( query ) NEW_LINE