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
using System ; using System . Collections . Generic ; class GFG { static readonly int N = 100001 ; static List < int > [ ] adj = new List < int > [ N ] ; static int [ ] a = new int [ N ] ; static int [ ] ans = new int [ N ] ; static bool 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 ; foreach ( int i in 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 List < int > ( ) ; 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 ++ ) { Console . Write ( ans [ q [ i ] ] + " ▁ " ) ; } } }