Store the maximum sum for every node by including it in a segment with its successors
function dfs1 ( u , par , g , weight ) { dp1 [ u ] = weight [ u ] ; for ( let c = 0 ; c < g [ u ] . length ; c ++ ) { if ( g [ u ] != par ) { dfs1 ( g [ u ] , u , g , weight ) ; dp1 [ u ] += Math . max ( 0 , dp1 [ g [ u ] ] ) ; } } }