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 ; 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
let dp1 = [ ] ; let dp2 = [ ] ; for ( let i = 0 ; i < 100005 ; i ++ ) { dp1 . push ( 0 ) ; dp2 . push ( 0 ) ; } 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 ] ] ) ; } } } function dfs2 ( u , par , g , weight ) { if ( par != 0 ) { maxSumAncestors = dp2 [ par ] - Math . max ( 0 , dp1 [ u ] ) ; dp2 [ u ] = dp1 [ u ] + Math . max ( 0 , maxSumAncestors ) ; } for ( let c = 0 ; c < g [ u ] . length ; c ++ ) { if ( g [ u ] != par ) { dfs2 ( g [ u ] , u , g , weight ) ; } } } function addEdge ( u , v , g ) { g [ u ] . push ( v ) ; g [ v ] . push ( u ) ; } function maxSumSegments ( g , weight , n ) { dfs1 ( 1 , 0 , g , weight ) ; for ( let i = 1 ; i < n + 1 ; i ++ ) dp2 [ i ] = dp1 [ i ] ; dfs2 ( 1 , 0 , g , weight ) ; } function printAns ( n ) { for ( let i = 1 ; i < n ; i ++ ) document . write ( dp2 [ i ] + " " ) ; } let n = 7 , u = 0 , v = 0 ; let g = [ ] ; for ( let i = 0 ; i < 100005 ; i ++ ) { g . push ( [ ] ) ; } addEdge ( 1 , 2 , g ) ; addEdge ( 1 , 3 , g ) ; addEdge ( 2 , 4 , g ) ; addEdge ( 2 , 5 , g ) ; addEdge ( 3 , 6 , g ) ; addEdge ( 4 , 7 , g ) ; let weight = new Array ( n + 1 ) ; weight . fill ( 0 ) ; weight [ 1 ] = - 8 ; weight [ 2 ] = 9 ; weight [ 3 ] = 7 ; weight [ 4 ] = - 4 ; weight [ 5 ] = 5 ; weight [ 6 ] = - 10 ; weight [ 7 ] = - 6 ; maxSumSegments ( g , weight , n ) ; printAns ( n ) ;