Maximum cost of splitting given Binary Tree into two halves | C ++ program for the above approach ; To store the results and sum of all nodes in the array ; To create adjacency list ; Function to add edges into the adjacency list ; Recursive function that calculate the value of the cost of splitting the tree recursively ; Fetch the child of node - r ; Neglect if cur node is parent ; Add all values of nodes which are decendents of r ; The two trees formed are rooted at ' r ' with its decendents ; Check and replace if current product t1 * t2 is large ; Function to find the maximum cost after splitting the tree in 2 halves ; Find sum of values in all nodes ; Traverse edges to create adjacency list ; Function Call ; Driver Code ; Values in each node ; Given Edges
#include <bits/stdc++.h> NEW_LINE using namespace std ; int ans = 0 , allsum = 0 ; vector < int > edges [ 100001 ] ; void addedge ( int a , int b ) { edges [ a ] . push_back ( b ) ; edges [ b ] . push_back ( a ) ; } void findCost ( int r , int p , int arr [ ] ) { int i , cur ; for ( i = 0 ; i < edges [ r ] . size ( ) ; i ++ ) { cur = edges [ r ] . at ( i ) ; if ( cur == p ) continue ; findCost ( cur , r , arr ) ; arr [ r ] += arr [ cur ] ; } int t1 = arr [ r ] ; int t2 = allsum - t1 ; if ( t1 * t2 > ans ) { ans = t1 * t2 ; } } void maximumCost ( int r , int p , int N , int M , int arr [ ] , int Edges [ ] [ 2 ] ) { for ( int i = 0 ; i < N ; i ++ ) { allsum += arr [ i ] ; } for ( int i = 0 ; i < M ; i ++ ) { addedge ( Edges [ i ] [ 0 ] , Edges [ i ] [ 1 ] ) ; } findCost ( r , p , arr ) ; } int main ( ) { int a , b , N = 6 ; int arr [ ] = { 13 , 8 , 7 , 4 , 5 , 9 } ; int M = 5 ; int Edges [ ] [ 2 ] = { { 0 , 1 } , { 1 , 2 } , { 1 , 4 } , { 3 , 4 } , { 4 , 5 } } ; maximumCost ( 1 , -1 , N , M , arr , Edges ) ; cout << ans ; return 0 ; }