Count of nodes having odd divisors in the given subtree for Q queries | Java 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
import java . util . * ; class GFG { static final int N = 100001 ; static Vector < Integer > [ ] adj = new Vector [ N ] ; static int [ ] a = new int [ N ] ; static int [ ] ans = new int [ N ] ; static boolean hasOddNumberOfDivisors ( int n ) { if ( ( double ) Math . sqrt ( n ) == ( int ) Math . sqrt ( n ) ) return true ; return false ; } static int dfs ( int node , int parent ) { int count = 0 ; for ( int i : adj [ node ] ) { if ( i != parent ) { count += dfs ( i , node ) ; } } if ( hasOddNumberOfDivisors ( a [ node ] ) ) ++ count ; ans [ node ] = count ; return count ; } public static void main ( String [ ] args ) { int n = 5 ; int [ ] q = { 4 , 1 , 5 , 3 } ; for ( int i = 0 ; i < adj . length ; i ++ ) adj [ i ] = new Vector < Integer > ( ) ; adj [ 1 ] . add ( 2 ) ; adj [ 2 ] . add ( 1 ) ; adj [ 2 ] . add ( 3 ) ; adj [ 3 ] . add ( 2 ) ; adj [ 3 ] . add ( 4 ) ; adj [ 4 ] . add ( 3 ) ; adj [ 1 ] . add ( 5 ) ; adj [ 5 ] . add ( 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 . length ; i ++ ) { System . out . print ( ans [ q [ i ] ] + " ▁ " ) ; } } }