Store the maximum sum for every node by including it in a segment with its successors
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