Queries to calculate Bitwise OR of each subtree of a given node in an N | 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
N = 100005 ; NEW_LINE adj = [ [ ] for i in range ( N ) ] ; NEW_LINE answer = [ 0 for i in range ( N ) ] NEW_LINE def addEdgesToGraph ( Edges , N ) : NEW_LINE INDENT for i in range ( N - 1 ) : NEW_LINE INDENT u = Edges [ i ] [ 0 ] ; NEW_LINE v = Edges [ i ] [ 1 ] ; NEW_LINE adj [ u ] . append ( v ) ; NEW_LINE adj [ v ] . append ( u ) ; NEW_LINE DEDENT DEDENT def DFS ( node , parent , Val ) : NEW_LINE INDENT answer [ node ] = Val [ node ] ; NEW_LINE for child in adj [ node ] : NEW_LINE INDENT if ( child == parent ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT DFS ( child , node , Val ) ; NEW_LINE answer [ node ] = ( answer [ node ] answer [ child ] ) ; NEW_LINE DEDENT DEDENT def preprocess ( Val ) : NEW_LINE INDENT DFS ( 1 , - 1 , Val ) ; NEW_LINE DEDENT def findSubtreeOR ( Queries , Q , Val ) : NEW_LINE INDENT preprocess ( Val ) ; NEW_LINE for i in range ( Q ) : NEW_LINE INDENT print ( answer [ Queries [ i ] ] , end = ' ▁ ' ) NEW_LINE DEDENT DEDENT def findSubtreeORUtil ( N , Edges , Val , Queries , Q ) : NEW_LINE INDENT addEdgesToGraph ( Edges , N ) ; NEW_LINE findSubtreeOR ( Queries , Q , Val ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 5 ; NEW_LINE Edges = [ [ 1 , 2 ] , [ 1 , 3 ] , [ 3 , 4 ] , [ 3 , 5 ] ] ; NEW_LINE Val = [ 0 , 2 , 3 , 4 , 8 , 16 ] ; NEW_LINE Queries = [ 2 , 3 , 1 ] ; NEW_LINE Q = len ( Queries ) NEW_LINE findSubtreeORUtil ( N , Edges , Val , Queries , Q ) ; NEW_LINE DEDENT