Sum of the distances from every node to all other nodes is maximum | Python3 program to implement the above approach ; Function to add an edge to the tree ; Function to run DFS and calculate the height of the subtree below it ; Initially initialize with 1 ; Traverse for all nodes connected to node ; If node is not parent then recall dfs ; Add the size of the subtree beneath it ; Function to assign weights to edges to maximize the final sum ; Initialize it which stores the height of the subtree beneath it ; Call the DFS function to ; Sort the given array ; Stores the number of times an edge is part of a path ; Iterate for all edges and find the number of nodes on the left and on the right ; Node 1 ; Node 2 ; If the number of nodes below is less then the other will be n - dp [ node ] ; Second condition ; Sort the number of times an edges occurs in the path ; Find the summation of all those paths and return ; Driver code ; Add an edge 1 - 2 in the tree ; Add an edge 2 - 3 in the tree ; Add an edge 3 - 4 in the tree ; Add an edge 3 - 5 in the tree ; Array which gives the edges weight to be assigned
edges = [ [ ] for i in range ( 100 ) ] NEW_LINE tree = [ [ ] for i in range ( 100 ) ] NEW_LINE def addEdge ( x , y ) : NEW_LINE INDENT edges . append ( [ x , y ] ) NEW_LINE tree [ x ] . append ( y ) NEW_LINE tree [ y ] . append ( x ) NEW_LINE DEDENT def dfs ( node , parent , dp ) : NEW_LINE INDENT dp [ node ] = 1 NEW_LINE for it in tree [ node ] : NEW_LINE INDENT if ( it != parent ) : NEW_LINE INDENT dfs ( it , node , dp ) NEW_LINE dp [ node ] += dp [ it ] NEW_LINE DEDENT DEDENT DEDENT def maximizeSum ( a , n ) : NEW_LINE INDENT dp = [ 0 for i in range ( n + 1 ) ] NEW_LINE dfs ( 1 , 0 , dp ) NEW_LINE a = sorted ( a [ : - 1 ] ) NEW_LINE ans = [ ] NEW_LINE for it in edges : NEW_LINE INDENT if len ( it ) > 0 : NEW_LINE INDENT x = it [ 0 ] NEW_LINE y = it [ 1 ] NEW_LINE if ( dp [ x ] < dp [ y ] ) : NEW_LINE INDENT fi = dp [ x ] NEW_LINE sec = n - dp [ x ] NEW_LINE ans . append ( fi * sec ) NEW_LINE DEDENT else : NEW_LINE INDENT fi = dp [ y ] NEW_LINE sec = n - dp [ y ] NEW_LINE ans . append ( fi * sec ) NEW_LINE DEDENT DEDENT DEDENT ans = sorted ( ans ) NEW_LINE res = 0 NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT res += ans [ i ] * a [ i ] NEW_LINE DEDENT return res NEW_LINE DEDENT n = 5 NEW_LINE addEdge ( 1 , 2 ) NEW_LINE addEdge ( 1 , 3 ) NEW_LINE addEdge ( 3 , 4 ) NEW_LINE addEdge ( 3 , 5 ) NEW_LINE a = [ 6 , 3 , 1 , 9 , 3 ] NEW_LINE print ( maximizeSum ( a , n ) ) NEW_LINE