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
ans = 0 NEW_LINE allsum = 0 NEW_LINE edges = [ [ ] for i in range ( 100001 ) ] NEW_LINE def addedge ( a , b ) : NEW_LINE INDENT global edges NEW_LINE edges [ a ] . append ( b ) NEW_LINE edges [ b ] . append ( a ) NEW_LINE DEDENT def findCost ( r , p , arr ) : NEW_LINE INDENT global edges NEW_LINE global ans NEW_LINE global allsum NEW_LINE i = 0 NEW_LINE for i in range ( len ( edges [ r ] ) ) : NEW_LINE INDENT cur = edges [ r ] [ i ] NEW_LINE if ( cur == p ) : NEW_LINE INDENT continue NEW_LINE DEDENT findCost ( cur , r , arr ) NEW_LINE arr [ r ] += arr [ cur ] NEW_LINE DEDENT t1 = arr [ r ] NEW_LINE t2 = allsum - t1 NEW_LINE if ( t1 * t2 > ans ) : NEW_LINE INDENT ans = t1 * t2 NEW_LINE DEDENT DEDENT def maximumCost ( r , p , N , M , arr , Edges ) : NEW_LINE INDENT global allsum NEW_LINE for i in range ( N ) : NEW_LINE INDENT allsum += arr [ i ] NEW_LINE DEDENT for i in range ( M ) : NEW_LINE INDENT addedge ( Edges [ i ] [ 0 ] , Edges [ i ] [ 1 ] ) NEW_LINE DEDENT findCost ( r , p , arr ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 6 NEW_LINE arr = [ 13 , 8 , 7 , 4 , 5 , 9 ] NEW_LINE M = 5 NEW_LINE Edges = [ [ 0 , 1 ] , [ 1 , 2 ] , [ 1 , 4 ] , [ 3 , 4 ] , [ 4 , 5 ] ] NEW_LINE maximumCost ( 1 , - 1 , N , M , arr , Edges ) NEW_LINE print ( ans ) NEW_LINE DEDENT