Find number of edges that can be broken in a tree such that Bitwise OR of resulting two trees are equal | C ++ 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 ; push_back edges
#include <bits/stdc++.h> NEW_LINE using namespace std ; int m [ 1000 ] , x [ 22 ] ; int a [ 1000 ] [ 22 ] ; vector < vector < int > > g ; int ans = 0 ; void dfs ( int u , int p ) { for ( int i = 0 ; i < g [ u ] . size ( ) ; i ++ ) { int v = g [ u ] [ i ] ; if ( v != p ) { dfs ( v , u ) ; for ( int i = 0 ; i < 22 ; i ++ ) a [ u ] [ i ] += a [ v ] [ i ] ; } } int pp = 0 ; for ( int 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 ++ ; } int main ( ) { int n = 4 ; g . resize ( n + 1 ) ; m [ 1 ] = 1 ; m [ 2 ] = 3 ; m [ 3 ] = 2 ; m [ 4 ] = 3 ; for ( int i = 1 ; i <= n ; i ++ ) { int y = m [ i ] ; int k = 0 ; while ( y != 0 ) { int p = y % 2 ; if ( p == 1 ) { x [ k ] ++ ; a [ i ] [ k ] ++ ; } y = y / 2 ; k ++ ; } } g [ 1 ] . push_back ( 2 ) ; g [ 2 ] . push_back ( 1 ) ; g [ 1 ] . push_back ( 3 ) ; g [ 3 ] . push_back ( 1 ) ; g [ 1 ] . push_back ( 4 ) ; g [ 4 ] . push_back ( 1 ) ; dfs ( 1 , 0 ) ; cout << ( ans ) ; }