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
using System ; using System . Collections . Generic ; class GFG { static int ans = 0 , allsum = 0 ; static List < int > [ ] edges = new List < int > [ 100001 ] ; static void addedge ( int a , int b ) { edges [ a ] . Add ( b ) ; edges [ b ] . Add ( a ) ; } static void findCost ( int r , int p , int [ ] arr ) { int i , cur ; for ( i = 0 ; i < edges [ r ] . Count ; i ++ ) { cur = edges [ r ] [ 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 ; } } static void maximumCost ( int r , int p , int N , int M , int [ ] arr , int [ , ] Edges ) { 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 ) ; } public static void Main ( String [ ] args ) { int N = 6 ; int [ ] arr = { 13 , 8 , 7 , 4 , 5 , 9 } ; int M = 5 ; int [ , ] Edges = { { 0 , 1 } , { 1 , 2 } , { 1 , 4 } , { 3 , 4 } , { 4 , 5 } } ; for ( int i = 0 ; i < edges . Length ; i ++ ) edges [ i ] = new List < int > ( ) ; maximumCost ( 1 , - 1 , N , M , arr , Edges ) ; Console . Write ( ans ) ; } }