Store the maximum sum for every node by including it in a segment with its successors
void dfs1 ( int u , int par , vector < int > g [ ] , int weight [ ] ) { dp1 [ u ] = weight [ u ] ; for ( auto c : g [ u ] ) { if ( c != par ) { dfs1 ( c , u , g , weight ) ; dp1 [ u ] += max ( 0 , dp1 ) ; } } }