Dynamic Programming on Trees | Set | JavaScript 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 ; Number of nodes ; adjacency list ; create undirected edges initialize the tree given in the diagram ; values of node 1 , 2 , 3. ... 14 ; function call
var dp = Array ( 100 ) . fill ( 0 ) ; function dfs ( a , v , u , parent ) { dp [ u ] = a [ u - 1 ] ; var maximum = 0 ; for ( var child of v [ u ] ) { if ( child == parent ) continue ; dfs ( a , v , child , u ) ; maximum = Math . max ( maximum , dp [ child ] ) ; } dp [ u ] += maximum ; } function maximumValue ( a , v ) { dfs ( a , v , 1 , 0 ) ; return dp [ 1 ] ; } var n = 14 ; var v = Array . from ( Array ( n + 1 ) , ( ) => Array ( ) ) ; for ( var i = 0 ; i < v . length ; i ++ ) v [ i ] = [ ] ; v [ 1 ] . push ( 2 ) ; v [ 2 ] . push ( 1 ) ; v [ 1 ] . push ( 3 ) ; v [ 3 ] . push ( 1 ) ; v [ 1 ] . push ( 4 ) ; v [ 4 ] . push ( 1 ) ; v [ 2 ] . push ( 5 ) ; v [ 5 ] . push ( 2 ) ; v [ 2 ] . push ( 6 ) ; v [ 6 ] . push ( 2 ) ; v [ 3 ] . push ( 7 ) ; v [ 7 ] . push ( 3 ) ; v [ 4 ] . push ( 8 ) ; v [ 8 ] . push ( 4 ) ; v [ 4 ] . push ( 9 ) ; v [ 9 ] . push ( 4 ) ; v [ 4 ] . push ( 10 ) ; v [ 10 ] . push ( 4 ) ; v [ 5 ] . push ( 11 ) ; v [ 11 ] . push ( 5 ) ; v [ 5 ] . push ( 12 ) ; v [ 12 ] . push ( 5 ) ; v [ 7 ] . push ( 13 ) ; v [ 13 ] . push ( 7 ) ; v [ 7 ] . push ( 14 ) ; v [ 14 ] . push ( 7 ) ; var a = [ 3 , 2 , 1 , 10 , 1 , 3 , 9 , 1 , 5 , 3 , 4 , 5 , 9 , 8 ] ; document . write ( maximumValue ( a , v ) ) ;