Queries to calculate Bitwise OR of each subtree of a given node in an N | C ++ program for the above approach ; Maximum Number of nodes ; Adjacency list ; Stores Bitwise OR of each node ; Function to add edges to the Tree ; Traverse the edges ; Add edges ; Function to perform DFS Traversal on the given tree ; Initialize answer with bitwise OR of current node ; Iterate over each child of the current node ; Skip parent node ; Call DFS for each child ; Taking bitwise OR of the answer of the child to find node 's OR value ; Function to call DFS from the '= root for precomputing answers ; Function to calculate and print the Bitwise OR for Q queries ; Perform preprocessing ; Iterate over each given query ; Utility function to find and print bitwise OR for Q queries ; Function to add edges to graph ; Function call ; Driver Code ; Number of nodes ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 1e5 + 5 ; vector < int > adj [ N ] ; vector < int > answer ( N ) ; void addEdgesToGraph ( int Edges [ ] [ 2 ] , int N ) { for ( int i = 0 ; i < N - 1 ; i ++ ) { int u = Edges [ i ] [ 0 ] ; int v = Edges [ i ] [ 1 ] ; adj [ u ] . push_back ( v ) ; adj [ v ] . push_back ( u ) ; } } void DFS ( int node , int parent , int Val [ ] ) { answer [ node ] = Val [ node ] ; for ( int child : adj [ node ] ) { if ( child == parent ) continue ; DFS ( child , node , Val ) ; answer [ node ] = ( answer [ node ] answer [ child ] ) ; } } void preprocess ( int Val [ ] ) { DFS ( 1 , -1 , Val ) ; } void findSubtreeOR ( int Queries [ ] , int Q , int Val [ ] ) { preprocess ( Val ) ; for ( int i = 0 ; i < Q ; i ++ ) { cout << answer [ Queries [ i ] ] << ' ▁ ' ; } } void findSubtreeORUtil ( int N , int Edges [ ] [ 2 ] , int Val [ ] , int Queries [ ] , int Q ) { addEdgesToGraph ( Edges , N ) ; findSubtreeOR ( Queries , Q , Val ) ; } int main ( ) { int N = 5 ; int Edges [ ] [ 2 ] = { { 1 , 2 } , { 1 , 3 } , { 3 , 4 } , { 3 , 5 } } ; int Val [ ] = { 0 , 2 , 3 , 4 , 8 , 16 } ; int Queries [ ] = { 2 , 3 , 1 } ; int Q = sizeof ( Queries ) / sizeof ( Queries [ 0 ] ) ; findSubtreeORUtil ( N , Edges , Val , Queries , Q ) ; return 0 ; }