Count of nodes having odd divisors in the given subtree for Q queries | C ++ implementation to count the number of nodes having odd number of divisors for each query ; Adjacency list for tree . ; Array for values and answer at ith node . ; Function to check whether N has odd divisors or not ; DFS function to pre - compute the answers ; Initialize the count ; Repeat for every child ; Increase the count if current node has odd number of divisors ; Driver Code ; Adjacency List ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100001 NEW_LINE vector < int > adj [ N ] ; int a [ N ] , ans [ N ] ; bool hasOddNumberOfDivisors ( int n ) { if ( ( double ) sqrt ( n ) == ( int ) sqrt ( n ) ) return true ; return false ; } int dfs ( int node , int parent ) { int count = 0 ; for ( auto i = adj [ node ] . begin ( ) ; i != adj [ node ] . end ( ) ; ++ i ) { if ( * i != parent ) { count += dfs ( * i , node ) ; } } if ( hasOddNumberOfDivisors ( a [ node ] ) ) ++ count ; ans [ node ] = count ; return count ; } int main ( ) { int n = 5 , i ; vector < int > q = { 4 , 1 , 5 , 3 } ; adj [ 1 ] . push_back ( 2 ) ; adj [ 2 ] . push_back ( 1 ) ; adj [ 2 ] . push_back ( 3 ) ; adj [ 3 ] . push_back ( 2 ) ; adj [ 3 ] . push_back ( 4 ) ; adj [ 4 ] . push_back ( 3 ) ; adj [ 1 ] . push_back ( 5 ) ; adj [ 5 ] . push_back ( 1 ) ; a [ 1 ] = 4 ; a [ 2 ] = 9 ; a [ 3 ] = 14 ; a [ 4 ] = 100 ; a [ 5 ] = 5 ; dfs ( 1 , -1 ) ; for ( int i = 0 ; i < q . size ( ) ; i ++ ) { cout << ans [ q [ i ] ] << " ▁ " ; } return 0 ; }