Find GCD of each subtree of a given node in an N | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 1e5 + 5 ; vector < vector < int > > v ( N ) ; vector < int > val ( N ) ; vector < int > answer ( N ) ; int n ; int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } 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 ] ) ; } } void preprocess ( ) { DFS ( 1 , -1 ) ; } void findGCD ( int queries [ ] , int q ) { preprocess ( ) ; for ( int i = 0 ; i < q ; i ++ ) { int GCD = answer [ queries [ i ] ] ; cout << " For ▁ subtree ▁ of ▁ " << queries [ i ] << " , ▁ GCD ▁ = ▁ " << GCD << endl ; } } int main ( ) { n = 5 ; v [ 1 ] . push_back ( 2 ) ; v [ 2 ] . push_back ( 1 ) ; v [ 1 ] . push_back ( 3 ) ; v [ 3 ] . push_back ( 1 ) ; v [ 3 ] . push_back ( 4 ) ; v [ 4 ] . push_back ( 3 ) ; v [ 3 ] . push_back ( 5 ) ; v [ 5 ] . push_back ( 3 ) ; val [ 1 ] = 2 ; val [ 2 ] = 3 ; val [ 3 ] = 4 ; val [ 4 ] = 8 ; val [ 5 ] = 16 ; int queries [ ] = { 2 , 3 , 1 } ; int q = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; findGCD ( queries , q ) ; return 0 ; }