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
using System ; using System . Collections ; class GFG { public static void dfs ( int node , int parent , int [ ] dp1 , int [ ] dp2 , ArrayList [ ] adj , int [ ] tree ) { int sum1 = 0 , sum2 = 0 ; foreach ( int i in adj [ node ] ) { if ( i == parent ) continue ; dfs ( i , node , dp1 , dp2 , adj , tree ) ; sum1 += dp2 [ i ] ; sum2 += Math . Max ( dp1 [ i ] , dp2 [ i ] ) ; } dp1 [ node ] = tree [ node ] + sum1 ; dp2 [ node ] = sum2 ; } public static void Main ( string [ ] arg ) { int n = 5 ; ArrayList [ ] adj = new ArrayList [ n + 1 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) { adj [ i ] = new ArrayList ( ) ; } adj [ 1 ] . Add ( 2 ) ; adj [ 2 ] . Add ( 1 ) ; adj [ 1 ] . Add ( 3 ) ; adj [ 3 ] . Add ( 1 ) ; adj [ 2 ] . Add ( 4 ) ; adj [ 4 ] . Add ( 2 ) ; adj [ 2 ] . Add ( 5 ) ; adj [ 5 ] . Add ( 2 ) ; int [ ] tree = new int [ n + 1 ] ; tree [ 1 ] = 10 ; tree [ 2 ] = 5 ; tree [ 3 ] = 11 ; tree [ 4 ] = 6 ; tree [ 5 ] = 8 ; int [ ] dp1 = new int [ n + 1 ] ; int [ ] dp2 = new int [ n + 1 ] ; Array . Fill ( dp1 , 0 ) ; Array . Fill ( dp2 , 0 ) ; dfs ( 1 , 1 , dp1 , dp2 , adj , tree ) ; Console . Write ( " Maximum ▁ sum : ▁ " + Math . Max ( dp1 [ 1 ] , dp2 [ 1 ] ) ) ; } }