Find number of edges that can be broken in a tree such that Bitwise OR of resulting two trees are equal | Python3 implementation of the approach ; Function to perform simple DFS ; Finding the number of times each bit is set in all the values of a subtree rooted at v ; Checking for each bit whether the numbers with that particular bit as set are either zero in both the resulting trees or greater than zero in both the resulting trees ; Driver code ; Number of nodes ; ArrayList to store the tree ; Array to store the value of nodes ; Array to store the number of times each bit is set in all the values in complete tree ; Finding the set bits in the value of node i ; append edges
m , x = [ 0 ] * 1000 , [ 0 ] * 22 NEW_LINE a = [ [ 0 for i in range ( 22 ) ] for j in range ( 1000 ) ] NEW_LINE ans = 0 NEW_LINE def dfs ( u , p ) : NEW_LINE INDENT global ans NEW_LINE for i in range ( 0 , len ( g [ u ] ) ) : NEW_LINE INDENT v = g [ u ] [ i ] NEW_LINE if v != p : NEW_LINE INDENT dfs ( v , u ) NEW_LINE for i in range ( 0 , 22 ) : NEW_LINE INDENT a [ u ] [ i ] += a [ v ] [ i ] NEW_LINE DEDENT DEDENT DEDENT pp = 0 NEW_LINE for i in range ( 0 , 22 ) : NEW_LINE INDENT if ( not ( ( a [ u ] [ i ] > 0 and x [ i ] - a [ u ] [ i ] > 0 ) or ( a [ u ] [ i ] == 0 and x [ i ] == 0 ) ) ) : NEW_LINE INDENT pp = 1 NEW_LINE break NEW_LINE DEDENT DEDENT if pp == 0 : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 4 NEW_LINE g = [ [ ] for i in range ( n + 1 ) ] NEW_LINE m [ 1 ] = 1 NEW_LINE m [ 2 ] = 3 NEW_LINE m [ 3 ] = 2 NEW_LINE m [ 4 ] = 3 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT y , k = m [ i ] , 0 NEW_LINE while y != 0 : NEW_LINE INDENT p = y % 2 NEW_LINE if p == 1 : NEW_LINE INDENT x [ k ] += 1 NEW_LINE a [ i ] [ k ] += 1 NEW_LINE DEDENT y = y // 2 NEW_LINE k += 1 NEW_LINE DEDENT DEDENT g [ 1 ] . append ( 2 ) NEW_LINE g [ 2 ] . append ( 1 ) NEW_LINE g [ 1 ] . append ( 3 ) NEW_LINE g [ 3 ] . append ( 1 ) NEW_LINE g [ 1 ] . append ( 4 ) NEW_LINE g [ 4 ] . append ( 1 ) NEW_LINE dfs ( 1 , 0 ) NEW_LINE print ( ans ) NEW_LINE DEDENT