Delete Edge to minimize subtree sum difference | DFS method to traverse through edges , calculating subtree Sum at each node and updating the difference between subtrees ; loop for all neighbors except parent and aggregate Sum over all subtrees ; store Sum in current node 's  subtree index ; at one side subtree Sum is ' Sum ' and other side subtree Sum is ' totalSum ▁ - ▁ Sum ' so their difference will be totalSum - 2 * Sum , by which we 'll update res ; Method returns minimum subtree Sum difference ; Calculating total Sum of tree and initializing subtree Sum 's  by vertex values ; filling edge data structure ; calling DFS method at node 0 , with parent as - 1 ; Driver Code
def dfs ( u , parent , totalSum , edge , subtree , res ) : NEW_LINE INDENT Sum = subtree [ u ] NEW_LINE for i in range ( len ( edge [ u ] ) ) : NEW_LINE INDENT v = edge [ u ] [ i ] NEW_LINE if ( v != parent ) : NEW_LINE INDENT dfs ( v , u , totalSum , edge , subtree , res ) NEW_LINE Sum += subtree [ v ] NEW_LINE DEDENT DEDENT subtree [ u ] = Sum NEW_LINE if ( u != 0 and abs ( totalSum - 2 * Sum ) < res [ 0 ] ) : NEW_LINE INDENT res [ 0 ] = abs ( totalSum - 2 * Sum ) NEW_LINE DEDENT DEDENT def getMinSubtreeSumDifference ( vertex , edges , N ) : NEW_LINE INDENT totalSum = 0 NEW_LINE subtree = [ None ] * N NEW_LINE for i in range ( N ) : NEW_LINE INDENT subtree [ i ] = vertex [ i ] NEW_LINE totalSum += vertex [ i ] NEW_LINE DEDENT edge = [ [ ] for i in range ( N ) ] NEW_LINE for i in range ( N - 1 ) : NEW_LINE INDENT edge [ edges [ i ] [ 0 ] ] . append ( edges [ i ] [ 1 ] ) NEW_LINE edge [ edges [ i ] [ 1 ] ] . append ( edges [ i ] [ 0 ] ) NEW_LINE DEDENT res = [ 999999999999 ] NEW_LINE dfs ( 0 , - 1 , totalSum , edge , subtree , res ) NEW_LINE return res [ 0 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT vertex = [ 4 , 2 , 1 , 6 , 3 , 5 , 2 ] NEW_LINE edges = [ [ 0 , 1 ] , [ 0 , 2 ] , [ 0 , 3 ] , [ 2 , 4 ] , [ 2 , 5 ] , [ 3 , 6 ] ] NEW_LINE N = len ( vertex ) NEW_LINE print ( getMinSubtreeSumDifference ( vertex , edges , N ) ) NEW_LINE DEDENT