Maximize sum of minimum difference of divisors of nodes in N | Python3 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 math NEW_LINE sub = [ 0 for i in range ( 100005 ) ] NEW_LINE def minDivisorDifference ( n ) : NEW_LINE INDENT num1 = 0 NEW_LINE num2 = 0 NEW_LINE for i in range ( int ( math . sqrt ( n ) ) , n + 1 ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT num1 = i NEW_LINE num2 = n // i NEW_LINE break NEW_LINE DEDENT DEDENT return abs ( num1 - num2 ) NEW_LINE DEDENT def dfs ( g , u , par ) : NEW_LINE INDENT sub [ u ] = minDivisorDifference ( u ) NEW_LINE mx = 0 NEW_LINE for c in g [ u ] : NEW_LINE INDENT if ( c != par ) : NEW_LINE INDENT ans = dfs ( g , c , u ) NEW_LINE mx = max ( mx , ans ) NEW_LINE DEDENT DEDENT sub [ u ] += mx NEW_LINE return sub [ u ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT g = [ [ ] for i in range ( 100005 ) ] NEW_LINE edges = 6 NEW_LINE g [ 18 ] . append ( 7 ) NEW_LINE g [ 7 ] . append ( 18 ) NEW_LINE g [ 18 ] . append ( 15 ) NEW_LINE g [ 15 ] . append ( 18 ) NEW_LINE g [ 15 ] . append ( 2 ) NEW_LINE g [ 2 ] . append ( 15 ) NEW_LINE g [ 7 ] . append ( 4 ) NEW_LINE g [ 4 ] . append ( 7 ) NEW_LINE g [ 7 ] . append ( 12 ) NEW_LINE g [ 12 ] . append ( 7 ) NEW_LINE g [ 12 ] . append ( 9 ) NEW_LINE g [ 9 ] . append ( 12 ) NEW_LINE root = 18 NEW_LINE print ( dfs ( g , root , - 1 ) ) NEW_LINE DEDENT