Dynamic Programming on Trees | Set | C # code to find the maximum path sum ; function for dfs traversal and to store the maximum value in [ ] dp for every node till the leaves ; initially dp [ u ] is always a [ u ] ; stores the maximum value from nodes ; traverse the tree ; if child is parent , then we continue without recursing further ; call dfs for further traversal ; store the maximum of previous visited node and present visited node ; add the maximum value returned to the parent node ; function that returns the maximum value ; Driver Code ; Number of nodes ; adjacency list ; create undirected edges initialize the tree given in the diagram ; values of node 1 , 2 , 3. ... 14 ; function call
using System ; using System . Collections . Generic ; class GFG { static int [ ] dp = new int [ 100 ] ; static void dfs ( int [ ] a , List < int > [ ] v , int u , int parent ) { dp [ u ] = a [ u - 1 ] ; int maximum = 0 ; foreach ( int child in v [ u ] ) { if ( child == parent ) continue ; dfs ( a , v , child , u ) ; maximum = Math . Max ( maximum , dp [ child ] ) ; } dp [ u ] += maximum ; } static int maximumValue ( int [ ] a , List < int > [ ] v ) { dfs ( a , v , 1 , 0 ) ; return dp [ 1 ] ; } public static void Main ( String [ ] args ) { int n = 14 ; List < int > [ ] v = new List < int > [ n + 1 ] ; for ( int i = 0 ; i < v . Length ; i ++ ) v [ i ] = new List < int > ( ) ; v [ 1 ] . Add ( 2 ) ; v [ 2 ] . Add ( 1 ) ; v [ 1 ] . Add ( 3 ) ; v [ 3 ] . Add ( 1 ) ; v [ 1 ] . Add ( 4 ) ; v [ 4 ] . Add ( 1 ) ; v [ 2 ] . Add ( 5 ) ; v [ 5 ] . Add ( 2 ) ; v [ 2 ] . Add ( 6 ) ; v [ 6 ] . Add ( 2 ) ; v [ 3 ] . Add ( 7 ) ; v [ 7 ] . Add ( 3 ) ; v [ 4 ] . Add ( 8 ) ; v [ 8 ] . Add ( 4 ) ; v [ 4 ] . Add ( 9 ) ; v [ 9 ] . Add ( 4 ) ; v [ 4 ] . Add ( 10 ) ; v [ 10 ] . Add ( 4 ) ; v [ 5 ] . Add ( 11 ) ; v [ 11 ] . Add ( 5 ) ; v [ 5 ] . Add ( 12 ) ; v [ 12 ] . Add ( 5 ) ; v [ 7 ] . Add ( 13 ) ; v [ 13 ] . Add ( 7 ) ; v [ 7 ] . Add ( 14 ) ; v [ 14 ] . Add ( 7 ) ; int [ ] a = { 3 , 2 , 1 , 10 , 1 , 3 , 9 , 1 , 5 , 3 , 4 , 5 , 9 , 8 } ; Console . WriteLine ( maximumValue ( a , v ) ) ; } }