Sum of the distances from every node to all other nodes is maximum | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void addEdge ( vector < pair < int , int > > & edges , list < int > * tree , int x , int y ) { edges . push_back ( { x , y } ) ; tree [ x ] . push_back ( y ) ; tree [ y ] . push_back ( x ) ; } void dfs ( vector < pair < int , int > > & edges , list < int > * tree , int node , int parent , int dp [ ] ) { dp [ node ] = 1 ; for ( auto it : tree [ node ] ) { if ( it != parent ) { dfs ( edges , tree , it , node , dp ) ; dp [ node ] += dp [ it ] ; } } } int maximizeSum ( int a [ ] , vector < pair < int , int > > & edges , list < int > * tree , int n ) { int dp [ n + 1 ] = { 0 } ; dfs ( edges , tree , 1 , 0 , dp ) ; sort ( a , a + ( n - 1 ) ) ; vector < int > ans ; for ( auto it : edges ) { int x = it . first ; int y = it . second ; if ( dp [ x ] < dp [ y ] ) { int fi = dp [ x ] ; int sec = n - dp [ x ] ; ans . push_back ( fi * sec ) ; } else { int fi = dp [ y ] ; int sec = n - dp [ y ] ; ans . push_back ( fi * sec ) ; } } sort ( ans . begin ( ) , ans . end ( ) ) ; int res = 0 ; for ( int i = 0 ; i < n - 1 ; i ++ ) { res += ans [ i ] * a [ i ] ; } return res ; } int main ( ) { int n = 5 ; vector < pair < int , int > > edges ; list < int > * tree = new list < int > [ n + 1 ] ; addEdge ( edges , tree , 1 , 2 ) ; addEdge ( edges , tree , 1 , 3 ) ; addEdge ( edges , tree , 3 , 4 ) ; addEdge ( edges , tree , 3 , 5 ) ; int a [ ] = { 6 , 3 , 1 , 9 , 3 } ; cout << maximizeSum ( a , edges , tree , n ) ; }