Count of nodes having odd divisors in the given subtree for Q queries | Javascript 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
let N = 100001 ; let adj = new Array ( N ) ; let a = new Array ( N ) ; let ans = new Array ( N ) ; function hasOddNumberOfDivisors ( n ) { if ( Math . sqrt ( n ) == parseInt ( Math . sqrt ( n ) , 10 ) ) return true ; return false ; } function dfs ( node , parent ) { let count = 0 ; for ( let i = 0 ; i < adj [ node ] . length ; i ++ ) { if ( adj [ node ] [ i ] != parent ) { count += dfs ( adj [ node ] [ i ] , node ) ; } } if ( hasOddNumberOfDivisors ( a [ node ] ) ) ++ count ; ans [ node ] = count ; return count ; } let n = 5 ; let q = [ 4 , 1 , 5 , 3 ] ; for ( let i = 0 ; i < adj . length ; i ++ ) adj [ i ] = [ ] ; adj [ 1 ] . push ( 2 ) ; adj [ 2 ] . push ( 1 ) ; adj [ 2 ] . push ( 3 ) ; adj [ 3 ] . push ( 2 ) ; adj [ 3 ] . push ( 4 ) ; adj [ 4 ] . push ( 3 ) ; adj [ 1 ] . push ( 5 ) ; adj [ 5 ] . push ( 1 ) ; a [ 1 ] = 4 ; a [ 2 ] = 9 ; a [ 3 ] = 14 ; a [ 4 ] = 100 ; a [ 5 ] = 5 ; dfs ( 1 , - 1 ) ; for ( let i = 0 ; i < q . length ; i ++ ) { document . write ( ans [ q [ i ] ] + " " ) ; }