Maximum cost of splitting given Binary Tree into two halves | 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
let ans = 0 , allsum = 0 ; let edges = new Array ( 100001 ) ; function addedge ( a , b ) { edges [ a ] . push ( b ) ; edges [ b ] . push ( a ) ; } function findCost ( r , p , arr ) { let i , cur ; for ( i = 0 ; i < edges [ r ] . length ; i ++ ) { cur = edges [ r ] [ i ] ; if ( cur == p ) continue ; findCost ( cur , r , arr ) ; arr [ r ] += arr [ cur ] ; } let t1 = arr [ r ] ; let t2 = allsum - t1 ; if ( t1 * t2 > ans ) { ans = t1 * t2 ; } } function maximumCost ( r , p , N , M , arr , Edges ) { for ( let i = 0 ; i < N ; i ++ ) { allsum += arr [ i ] ; } for ( let i = 0 ; i < M ; i ++ ) { addedge ( Edges [ i ] [ 0 ] , Edges [ i ] [ 1 ] ) ; } findCost ( r , p , arr ) ; } let N = 6 ; let arr = [ 13 , 8 , 7 , 4 , 5 , 9 ] ; let M = 5 ; let Edges = [ [ 0 , 1 ] , [ 1 , 2 ] , [ 1 , 4 ] , [ 3 , 4 ] , [ 4 , 5 ] ] ; for ( let i = 0 ; i < edges . length ; i ++ ) edges [ i ] = [ ] ; maximumCost ( 1 , - 1 , N , M , arr , Edges ) ; document . write ( ans ) ;