Maximize sum of minimum difference of divisors of nodes in N | Array to store the result at each node ; Function to get minimum difference between the divisors of a number ; Iterate from square root of N to N ; return absolute difference ; DFS function to calculate the maximum sum ; Store the min difference ; Add the maximum of all children to sub [ u ] ; Return maximum sum of node ' u ' to its parent ; Driver code
let sub = new Array ( 100005 ) ; sub . fill ( 0 ) ; function minDivisorDifference ( n ) { let num1 = 0 ; let num2 = 0 ; for ( let i = parseInt ( Math . sqrt ( n ) , 10 ) ; i <= n ; i ++ ) { if ( n % i == 0 ) { num1 = i ; num2 = parseInt ( n / i , 10 ) ; break ; } } return Math . abs ( num1 - num2 ) ; } function dfs ( g , u , par ) { sub [ u ] = minDivisorDifference ( u ) ; let mx = 0 ; for ( let c = 0 ; c < g [ u ] . length ; c ++ ) { if ( g [ u ] != par ) { let ans = dfs ( g , g [ u ] , u ) ; mx = Math . max ( mx , ans ) ; } } sub [ u ] += mx ; return sub [ u ] ; } let g = new Array ( 100005 ) ; for ( let i = 0 ; i < g . length ; i ++ ) g [ i ] = [ ] ; let edges = 6 ; g [ 18 ] . push ( 7 ) ; g [ 7 ] . push ( 18 ) ; g [ 18 ] . push ( 15 ) ; g [ 15 ] . push ( 18 ) ; g [ 15 ] . push ( 2 ) ; g [ 2 ] . push ( 15 ) ; g [ 7 ] . push ( 4 ) ; g [ 4 ] . push ( 7 ) ; g [ 7 ] . push ( 12 ) ; g [ 12 ] . push ( 7 ) ; g [ 12 ] . push ( 9 ) ; g [ 9 ] . push ( 12 ) ; let root = 18 ; document . write ( dfs ( g , root , - 1 ) ) ;