Find GCD of each subtree of a given node in an N | Java program to find GCD of each subtree for a given node by Q queries ; 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 ; Driver code ; Tree : 1 ( 2 ) / \ 2 ( 3 ) 3 ( 4 ) / \ 4 ( 8 ) 5 ( 16 ) ; Making a undirected tree ; Values associated with nodes ; Function call
import java . util . * ; class GFG { static int N = ( int ) ( 1e5 + 5 ) ; static Vector < Integer > [ ] v = new Vector [ N ] ; static int [ ] val = new int [ N ] ; static int [ ] answer = new int [ N ] ; static int n ; static int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } static void DFS ( int node , int parent ) { answer [ node ] = val [ node ] ; for ( int child : v [ node ] ) { if ( child == parent ) continue ; DFS ( child , node ) ; answer [ node ] = gcd ( answer [ node ] , answer [ child ] ) ; } } static void preprocess ( ) { DFS ( 1 , - 1 ) ; } static void findGCD ( int queries [ ] , int q ) { preprocess ( ) ; for ( int i = 0 ; i < q ; i ++ ) { int GCD = answer [ queries [ i ] ] ; System . out . print ( " For ▁ subtree ▁ of ▁ " + queries [ i ] + " , ▁ GCD ▁ = ▁ " + GCD + "NEW_LINE"); } } public static void main ( String [ ] args ) { n = 5 ; for ( int i = 0 ; i < v . length ; i ++ ) v [ i ] = new Vector < Integer > ( ) ; v [ 1 ] . add ( 2 ) ; v [ 2 ] . add ( 1 ) ; v [ 1 ] . add ( 3 ) ; v [ 3 ] . add ( 1 ) ; v [ 3 ] . add ( 4 ) ; v [ 4 ] . add ( 3 ) ; v [ 3 ] . add ( 5 ) ; v [ 5 ] . add ( 3 ) ; val [ 1 ] = 2 ; val [ 2 ] = 3 ; val [ 3 ] = 4 ; val [ 4 ] = 8 ; val [ 5 ] = 16 ; int queries [ ] = { 2 , 3 , 1 } ; int q = queries . length ; findGCD ( queries , q ) ; } }