Find GCD of each subtree of a given node in an N | Maximum number of nodes ; Tree represented as adjacency list ; For storing value associates with node ; For storing GCD of every subarray ; Number of nodes ; Function to find GCD of two numbers . Using Euclidean algo ; If b == 0 then simply return a ; DFS function to traverse the tree ; Initializing answer with GCD of this node . ; Iterate over each child of current node ; Skipping the parent ; Call DFS for each child ; Taking GCD of the answer of the child to find node 's GCD ; Calling DFS from the root ( 1 ) for precomputing answers ; Function to find and prGCD for Q queries ; Doing preprocessing ; Iterate over each given query ; Driver code ; Tree : 1 ( 2 ) / \ 2 ( 3 ) 3 ( 4 ) / \ 4 ( 8 ) 5 ( 16 ) ; Making a undirected tree ; Values associated with nodes ; Function call
N = 10 ** 5 + 5 NEW_LINE v = [ [ ] for i in range ( N ) ] NEW_LINE val = [ 0 ] * ( N ) NEW_LINE answer = [ 0 ] * ( N ) NEW_LINE n = 0 NEW_LINE def gcd ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT return gcd ( b , a % b ) NEW_LINE DEDENT def DFS ( node , parent ) : NEW_LINE INDENT answer [ node ] = val [ node ] NEW_LINE for child in v [ node ] : NEW_LINE INDENT if ( child == parent ) : NEW_LINE INDENT continue NEW_LINE DEDENT DFS ( child , node ) NEW_LINE answer [ node ] = gcd ( answer [ node ] , answer [ child ] ) NEW_LINE DEDENT DEDENT def preprocess ( ) : NEW_LINE INDENT DFS ( 1 , - 1 ) NEW_LINE DEDENT def findGCD ( queries , q ) : NEW_LINE INDENT preprocess ( ) NEW_LINE for i in range ( q ) : NEW_LINE INDENT GCD = answer [ queries [ i ] ] NEW_LINE print ( " For ▁ subtree ▁ of ▁ " , queries [ i ] , " , ▁ GCD ▁ = ▁ " , GCD ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 5 NEW_LINE v [ 1 ] . append ( 2 ) NEW_LINE v [ 2 ] . append ( 1 ) NEW_LINE v [ 1 ] . append ( 3 ) NEW_LINE v [ 3 ] . append ( 1 ) NEW_LINE v [ 3 ] . append ( 4 ) NEW_LINE v [ 4 ] . append ( 3 ) NEW_LINE v [ 3 ] . append ( 5 ) NEW_LINE v [ 5 ] . append ( 3 ) NEW_LINE val [ 1 ] = 2 NEW_LINE val [ 2 ] = 3 NEW_LINE val [ 3 ] = 4 NEW_LINE val [ 4 ] = 8 NEW_LINE val [ 5 ] = 16 NEW_LINE queries = [ 2 , 3 , 1 ] NEW_LINE q = len ( queries ) NEW_LINE findGCD ( queries , q ) NEW_LINE DEDENT