Find number of edges that can be broken in a tree such that Bitwise OR of resulting two trees are equal | JavaScript 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 ; 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 of a subtree ; 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 ; add edges
var m = [ ] ; var a = [ ] ; var x = [ ] ; var g = [ ] ; var ans = 0 ; function dfs ( u , p ) { for ( var v of g [ u ] ) { if ( v != p ) { dfs ( v , u ) ; for ( var i = 0 ; i < 22 ; i ++ ) a [ u ] [ i ] += a [ v ] [ i ] ; } } var pp = 0 ; for ( var i = 0 ; i < 22 ; i ++ ) { if ( ! ( ( a [ u ] [ i ] > 0 && x [ i ] - a [ u ] [ i ] > 0 ) || ( a [ u ] [ i ] == 0 && x [ i ] == 0 ) ) ) { pp = 1 ; break ; } } if ( pp == 0 ) ans ++ ; } var n = 4 ; g = Array . from ( Array ( n + 1 ) , ( ) => Array ( ) . fill ( 0 ) ) ; m = Array ( n + 1 ) ; m [ 1 ] = 1 ; m [ 2 ] = 3 ; m [ 3 ] = 2 ; m [ 4 ] = 3 ; a = Array . from ( Array ( n + 1 ) , ( ) => Array ( 22 ) . fill ( 0 ) ) ; x = Array ( 22 ) . fill ( 0 ) ; for ( var i = 1 ; i <= n ; i ++ ) { g [ i ] = [ ] ; var y = m [ i ] ; var k = 0 ; while ( y != 0 ) { var p = y % 2 ; if ( p == 1 ) { x [ k ] ++ ; a [ i ] [ k ] ++ ; } y = parseInt ( y / 2 ) ; k ++ ; } } g [ 1 ] . push ( 2 ) ; g [ 2 ] . push ( 1 ) ; g [ 1 ] . push ( 3 ) ; g [ 3 ] . push ( 1 ) ; g [ 1 ] . push ( 4 ) ; g [ 4 ] . push ( 1 ) ; dfs ( 1 , 0 ) ; document . write ( ans ) ;