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 print GCD for Q queries ; Doing preprocessing ; Iterate over each given query ; Tree : 1 ( 2 ) / \ 2 ( 3 ) 3 ( 4 ) / \ 4 ( 8 ) 5 ( 16 ) ; Making a undirected tree ; Values associated with nodes ; Function call
var N = 100005 ; var v = Array . from ( Array ( N ) , ( ) => Array ( ) ) ; var val = Array ( N ) ; var answer = Array ( N ) ; var n ; function gcd ( a , b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } function DFS ( node , parent ) { answer [ node ] = val [ node ] ; v [ node ] . forEach ( child => { if ( child != parent ) { DFS ( child , node ) ; answer [ node ] = gcd ( answer [ node ] , answer [ child ] ) ; } } ) ; } function preprocess ( ) { DFS ( 1 , - 1 ) ; } function findGCD ( queries , q ) { preprocess ( ) ; for ( var i = 0 ; i < q ; i ++ ) { var GCD = answer [ queries [ i ] ] ; document . write ( " " + queries [ i ] + " " + GCD + " " ) ; } } n = 5 ; v [ 1 ] . push ( 2 ) ; v [ 2 ] . push ( 1 ) ; v [ 1 ] . push ( 3 ) ; v [ 3 ] . push ( 1 ) ; v [ 3 ] . push ( 4 ) ; v [ 4 ] . push ( 3 ) ; v [ 3 ] . push ( 5 ) ; v [ 5 ] . push ( 3 ) ; val [ 1 ] = 2 ; val [ 2 ] = 3 ; val [ 3 ] = 4 ; val [ 4 ] = 8 ; val [ 5 ] = 16 ; var queries = [ 2 , 3 , 1 ] ; var q = queries . length ; findGCD ( queries , q ) ;