Maximum sum possible for every node by including it in a segment of N | C ++ 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 ; Driver Program ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp1 [ 100005 ] ; int dp2 [ 100005 ] ; 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 ) ; } } } void dfs2 ( int u , int par , vector < int > g [ ] , int weight [ ] ) { if ( par != 0 ) { int maxSumAncestors = dp2 [ par ] - max ( 0 , dp1 [ u ] ) ; dp2 [ u ] = dp1 [ u ] + max ( 0 , maxSumAncestors ) ; } for ( auto c : g [ u ] ) { if ( c != par ) { dfs2 ( c , u , g , weight ) ; } } } void addEdge ( int u , int v , vector < int > g [ ] ) { g [ u ] . push_back ( v ) ; g [ v ] . push_back ( u ) ; } void maxSumSegments ( vector < int > g [ ] , int weight [ ] , int n ) { dfs1 ( 1 , 0 , g , weight ) ; for ( int i = 1 ; i <= n ; i ++ ) { dp2 [ i ] = dp1 [ i ] ; } dfs2 ( 1 , 0 , g , weight ) ; } void printAns ( int n ) { for ( int i = 1 ; i <= n ; i ++ ) { cout << dp2 [ i ] << " ▁ " ; } } int main ( ) { int n = 6 ; int u , v ; vector < int > g [ 100005 ] ; 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 [ 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 ) ; return 0 ; }