Dynamic Programming on Trees | Set | Python3 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 as a dictionary ; Create undirected edges initialize the tree given in the diagram ; Values of node 1 , 2 , 3. ... 14 ; Function call
dp = [ 0 ] * 100 NEW_LINE def dfs ( a , v , u , parent ) : NEW_LINE INDENT dp [ u ] = a [ u - 1 ] NEW_LINE maximum = 0 NEW_LINE for child in v [ u ] : NEW_LINE INDENT if child == parent : NEW_LINE INDENT continue NEW_LINE DEDENT dfs ( a , v , child , u ) NEW_LINE maximum = max ( maximum , dp [ child ] ) NEW_LINE DEDENT dp [ u ] += maximum NEW_LINE DEDENT def maximumValue ( a , v ) : NEW_LINE INDENT dfs ( a , v , 1 , 0 ) NEW_LINE return dp [ 1 ] NEW_LINE DEDENT def main ( ) : NEW_LINE INDENT n = 14 NEW_LINE v = { } NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT v [ i ] = [ ] NEW_LINE DEDENT v [ 1 ] . append ( 2 ) , v [ 2 ] . append ( 1 ) NEW_LINE v [ 1 ] . append ( 3 ) , v [ 3 ] . append ( 1 ) NEW_LINE v [ 1 ] . append ( 4 ) , v [ 4 ] . append ( 1 ) NEW_LINE v [ 2 ] . append ( 5 ) , v [ 5 ] . append ( 2 ) NEW_LINE v [ 2 ] . append ( 6 ) , v [ 6 ] . append ( 2 ) NEW_LINE v [ 3 ] . append ( 7 ) , v [ 7 ] . append ( 3 ) NEW_LINE v [ 4 ] . append ( 8 ) , v [ 8 ] . append ( 4 ) NEW_LINE v [ 4 ] . append ( 9 ) , v [ 9 ] . append ( 4 ) NEW_LINE v [ 4 ] . append ( 10 ) , v [ 10 ] . append ( 4 ) NEW_LINE v [ 5 ] . append ( 11 ) , v [ 11 ] . append ( 5 ) NEW_LINE v [ 5 ] . append ( 12 ) , v [ 12 ] . append ( 5 ) NEW_LINE v [ 7 ] . append ( 13 ) , v [ 13 ] . append ( 7 ) NEW_LINE v [ 7 ] . append ( 14 ) , v [ 14 ] . append ( 7 ) NEW_LINE a = [ 3 , 2 , 1 , 10 , 1 , 3 , 9 , 1 , 5 , 3 , 4 , 5 , 9 , 8 ] NEW_LINE print ( maximumValue ( a , v ) ) NEW_LINE DEDENT main ( ) NEW_LINE