Maximum sum of nodes in Binary tree such that no two are adjacent | Dynamic Programming | C ++ program to find maximum sum of a subset of nodes that are not adjacent ; Function to find the diameter of the tree using Dynamic Programming ; Traverse for all children of node ; Call DFS function again ; Include the current node then donot include the children ; Donot include current node , then include children or not include them ; Recurrence value ; Driver program to test above functions ; Constructed tree is 1 / \ 2 3 / \ 4 5 ; create undirected edges ; Numbers to node ; Find maximum sum by calling function
#include <bits/stdc++.h> NEW_LINE using namespace std ; void dfs ( int node , int parent , int dp1 [ ] , int dp2 [ ] , list < int > * adj , int tree [ ] ) { int sum1 = 0 , sum2 = 0 ; for ( auto i = adj [ node ] . begin ( ) ; i != adj [ node ] . end ( ) ; ++ i ) { if ( * i == parent ) continue ; dfs ( * i , node , dp1 , dp2 , adj , tree ) ; sum1 += dp2 [ * i ] ; sum2 += max ( dp1 [ * i ] , dp2 [ * i ] ) ; } dp1 [ node ] = tree [ node ] + sum1 ; dp2 [ node ] = sum2 ; } int main ( ) { int n = 5 ; list < int > * adj = new list < int > [ n + 1 ] ; adj [ 1 ] . push_back ( 2 ) ; adj [ 2 ] . push_back ( 1 ) ; adj [ 1 ] . push_back ( 3 ) ; adj [ 3 ] . push_back ( 1 ) ; adj [ 2 ] . push_back ( 4 ) ; adj [ 4 ] . push_back ( 2 ) ; adj [ 2 ] . push_back ( 5 ) ; adj [ 5 ] . push_back ( 2 ) ; int tree [ n + 1 ] ; tree [ 1 ] = 10 ; tree [ 2 ] = 5 ; tree [ 3 ] = 11 ; tree [ 4 ] = 6 ; tree [ 5 ] = 8 ; int dp1 [ n + 1 ] , dp2 [ n + 1 ] ; memset ( dp1 , 0 , sizeof dp1 ) ; memset ( dp2 , 0 , sizeof dp2 ) ; dfs ( 1 , 1 , dp1 , dp2 , adj , tree ) ; cout << " Maximum ▁ sum : ▁ " << max ( dp1 [ 1 ] , dp2 [ 1 ] ) << endl ; return 0 ; }