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