Largest subtree sum for each vertex of given N | Python3 program for the above approach ; Function to perform the DFS Traversal on the given Tree ; To check if v is leaf vertex ; Initialize answer for vertex v ; Traverse adjacency list of v ; Update maximum subtree sum ; If v is leaf ; Function to calculate maximum subtree sum for each vertex ; Add Edegs to the list ; Calculate answer ; Prthe result ; Driver Code ; Given nodes ; Give N edges ; Given values ; Function Call
V = 3 NEW_LINE M = 2 NEW_LINE def dfs ( v , p ) : NEW_LINE INDENT isLeaf = 1 NEW_LINE ans [ v ] = - 10 ** 9 NEW_LINE for u in adj [ v ] : NEW_LINE INDENT if ( u == p ) : NEW_LINE INDENT continue NEW_LINE DEDENT isLeaf = 0 NEW_LINE dfs ( u , v ) NEW_LINE ans [ v ] = max ( ans [ u ] + vals [ v ] , max ( ans [ u ] , vals [ u ] ) ) NEW_LINE DEDENT if ( isLeaf ) : NEW_LINE INDENT ans [ v ] = vals [ v ] NEW_LINE DEDENT DEDENT def printAnswer ( n , edges , vals ) : NEW_LINE INDENT for i in range ( n - 1 ) : NEW_LINE INDENT u = edges [ i ] [ 0 ] - 1 NEW_LINE v = edges [ i ] [ 1 ] - 1 NEW_LINE adj [ u ] . append ( v ) NEW_LINE adj [ v ] . append ( u ) NEW_LINE DEDENT dfs ( 0 , - 1 ) NEW_LINE for x in ans : NEW_LINE INDENT print ( x , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 4 NEW_LINE edges = [ [ 1 , 2 ] , [ 1 , 3 ] , [ 3 , 4 ] ] NEW_LINE adj = [ [ ] for i in range ( N ) ] NEW_LINE ans = [ 0 for i in range ( N ) ] NEW_LINE vals = [ 1 , - 1 , 0 , 1 ] NEW_LINE printAnswer ( N , edges , vals ) NEW_LINE DEDENT