Maximum sum possible for every node by including it in a segment of N | Java program to calculate the maximum sum possible for every node by including it in a segment of the N - Ary Tree ; 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
import java . util . * ; public class Main { static int [ ] dp1 = new int [ 100005 ] ; static int [ ] dp2 = new int [ 100005 ] ; 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 ) ] ) ; } } } static void dfs2 ( int u , int par , Vector < Vector < Integer > > g , int [ ] weight ) { if ( par != 0 ) { int maxSumAncestors = dp2 [ par ] - Math . max ( 0 , dp1 [ u ] ) ; dp2 [ u ] = dp1 [ u ] + Math . max ( 0 , maxSumAncestors ) ; } for ( int c = 0 ; c < g . get ( u ) . size ( ) ; c ++ ) { if ( g . get ( u ) . get ( c ) != par ) { dfs2 ( g . get ( u ) . get ( c ) , u , g , weight ) ; } } } static void addEdge ( int u , int v , Vector < Vector < Integer > > g ) { g . get ( u ) . add ( v ) ; g . get ( v ) . add ( u ) ; } static void maxSumSegments ( Vector < Vector < Integer > > g , int [ ] weight , int n ) { dfs1 ( 1 , 0 , g , weight ) ; for ( int i = 1 ; i < n + 1 ; i ++ ) dp2 [ i ] = dp1 [ i ] ; dfs2 ( 1 , 0 , g , weight ) ; } static void printAns ( int n ) { for ( int i = 1 ; i < n ; i ++ ) System . out . print ( dp2 [ i ] + " ▁ " ) ; } public static void main ( String [ ] args ) { int n = 7 ; Vector < Vector < Integer > > g = new Vector < Vector < Integer > > ( ) ; for ( int i = 0 ; i < 100005 ; i ++ ) { g . add ( new Vector < Integer > ( ) ) ; } addEdge ( 1 , 2 , g ) ; addEdge ( 1 , 3 , g ) ; addEdge ( 2 , 4 , g ) ; addEdge ( 2 , 5 , g ) ; addEdge ( 3 , 6 , g ) ; addEdge ( 4 , 7 , g ) ; int [ ] weight = new int [ n + 1 ] ; 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 ) ; } }