Maximum sum possible for every node by including it in a segment of N | Stores the maximum sum possible for every node by including them in a segment with their successors ; Stores the maximum sum possible for every node by including them in a segment with their ancestors ; Store the maximum sum for every node by including it in a segment with its successors ; Update the maximum sums for each node by including them in a sequence with their ancestors ; Condition to check , if current node is not root ; Add edges ; Function to find the maximum answer for each node ; Compute the maximum sums with successors ; Store the computed maximums ; Update the maximum sums by including their ancestors ; Print the desired result ; Driver code ; Number of nodes ; Graph ; Add edges ; Weight of each node ; Compute the max sum of segments for each node ; Print the answer for every node
dp1 = [ 0 for i in range ( 100005 ) ] NEW_LINE dp2 = [ 0 for i in range ( 100005 ) ] NEW_LINE def dfs1 ( u , par , g , weight ) : NEW_LINE INDENT dp1 [ u ] = weight [ u ] NEW_LINE for c in g [ u ] : NEW_LINE INDENT if ( c != par ) : NEW_LINE INDENT dfs1 ( c , u , g , weight ) NEW_LINE dp1 [ u ] += max ( 0 , dp1 ) NEW_LINE DEDENT DEDENT DEDENT def dfs2 ( u , par , g , weight ) : NEW_LINE INDENT if ( par != 0 ) : NEW_LINE INDENT maxSumAncestors = dp2 [ par ] - max ( 0 , dp1 [ u ] ) NEW_LINE dp2 [ u ] = dp1 [ u ] + max ( 0 , maxSumAncestors ) NEW_LINE DEDENT for c in g [ u ] : NEW_LINE INDENT if ( c != par ) : NEW_LINE INDENT dfs2 ( c , u , g , weight ) NEW_LINE DEDENT DEDENT DEDENT def addEdge ( u , v , g ) : NEW_LINE INDENT g [ u ] . append ( v ) NEW_LINE g [ v ] . append ( u ) NEW_LINE DEDENT def maxSumSegments ( g , weight , n ) : NEW_LINE INDENT dfs1 ( 1 , 0 , g , weight ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT dp2 [ i ] = dp1 [ i ] NEW_LINE DEDENT dfs2 ( 1 , 0 , g , weight ) NEW_LINE DEDENT def printAns ( n ) : NEW_LINE INDENT for i in range ( 1 , n ) : NEW_LINE INDENT print ( dp2 [ i ] , end = ' ▁ ' ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 7 NEW_LINE u = 0 NEW_LINE v = 0 NEW_LINE g = [ [ ] for i in range ( 100005 ) ] NEW_LINE addEdge ( 1 , 2 , g ) NEW_LINE addEdge ( 1 , 3 , g ) NEW_LINE addEdge ( 2 , 4 , g ) NEW_LINE addEdge ( 2 , 5 , g ) NEW_LINE addEdge ( 3 , 6 , g ) NEW_LINE addEdge ( 4 , 7 , g ) NEW_LINE weight = [ 0 for i in range ( n + 1 ) ] NEW_LINE weight [ 1 ] = - 8 NEW_LINE weight [ 2 ] = 9 NEW_LINE weight [ 3 ] = 7 NEW_LINE weight [ 4 ] = - 4 NEW_LINE weight [ 5 ] = 5 NEW_LINE weight [ 6 ] = - 10 NEW_LINE weight [ 7 ] = - 6 NEW_LINE maxSumSegments ( g , weight , n ) NEW_LINE printAns ( n ) NEW_LINE DEDENT