Maximize sum of minimum difference of divisors of nodes in N | Java program to maximize the sum of minimum difference of divisors of nodes in an n - ary tree ; 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
import java . util . Vector ; class GFG { static int [ ] sub = new int [ 100005 ] ; static int minDivisorDifference ( int n ) { int num1 = 0 ; int num2 = 0 ; for ( int i = ( int ) Math . sqrt ( n ) ; i <= n ; i ++ ) { if ( n % i == 0 ) { num1 = i ; num2 = n / i ; break ; } } return Math . abs ( num1 - num2 ) ; } static int dfs ( Vector < Integer > g [ ] , int u , int par ) { sub [ u ] = minDivisorDifference ( u ) ; int mx = 0 ; for ( int c : g [ u ] ) { if ( c != par ) { int ans = dfs ( g , c , u ) ; mx = Math . max ( mx , ans ) ; } } sub [ u ] += mx ; return sub [ u ] ; } public static void main ( String [ ] args ) { @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] g = new Vector [ 100005 ] ; for ( int i = 0 ; i < g . length ; i ++ ) g [ i ] = new Vector < Integer > ( ) ; int edges = 6 ; g [ 18 ] . add ( 7 ) ; g [ 7 ] . add ( 18 ) ; g [ 18 ] . add ( 15 ) ; g [ 15 ] . add ( 18 ) ; g [ 15 ] . add ( 2 ) ; g [ 2 ] . add ( 15 ) ; g [ 7 ] . add ( 4 ) ; g [ 4 ] . add ( 7 ) ; g [ 7 ] . add ( 12 ) ; g [ 12 ] . add ( 7 ) ; g [ 12 ] . add ( 9 ) ; g [ 9 ] . add ( 12 ) ; int root = 18 ; System . out . print ( dfs ( g , root , - 1 ) ) ; } }