Dynamic Programming on Trees | Set 2 | Python3 code to find the maximum path length considering any node as root ; function to pre - calculate the array inn [ ] which stores the maximum height when travelled via branches ; initially every node has 0 height ; traverse in the subtree of u ; if child is same as parent ; dfs called ; recursively calculate the max height ; function to pre - calculate the array ouut [ ] which stores the maximum height when traveled via parent ; stores the longest and second longest branches ; traverse in the subtress of u ; compare and store the longest and second longest ; traverse in the subtree of u ; if longest branch has the node , then consider the second longest branch ; recursively calculate out [ i ] ; dfs function call ; function to prall the maximum heights from every node ; traversal to calculate inn [ ] array ; traversal to calculate out [ ] array ; prall maximum heights ; Driver Code ; initialize the tree given in the diagram ; function to print the maximum height from every node
inn = [ 0 ] * 100 NEW_LINE out = [ 0 ] * 100 NEW_LINE def dfs1 ( v , u , parent ) : NEW_LINE INDENT global inn , out NEW_LINE inn [ u ] = 0 NEW_LINE for child in v [ u ] : NEW_LINE INDENT if ( child == parent ) : NEW_LINE INDENT continue NEW_LINE DEDENT dfs1 ( v , child , u ) NEW_LINE inn [ u ] = max ( inn [ u ] , 1 + inn [ child ] ) NEW_LINE DEDENT DEDENT def dfs2 ( v , u , parent ) : NEW_LINE INDENT global inn , out NEW_LINE mx1 , mx2 = - 1 , - 1 NEW_LINE for child in v [ u ] : NEW_LINE INDENT if ( child == parent ) : NEW_LINE INDENT continue NEW_LINE DEDENT if ( inn [ child ] >= mx1 ) : NEW_LINE INDENT mx2 = mx1 NEW_LINE mx1 = inn [ child ] NEW_LINE DEDENT elif ( inn [ child ] > mx2 ) : NEW_LINE INDENT mx2 = inn [ child ] NEW_LINE DEDENT DEDENT for child in v [ u ] : NEW_LINE INDENT if ( child == parent ) : NEW_LINE INDENT continue NEW_LINE DEDENT longest = mx1 NEW_LINE if ( mx1 == inn [ child ] ) : NEW_LINE INDENT longest = mx2 NEW_LINE DEDENT out [ child ] = 1 + max ( out [ u ] , 1 + longest ) NEW_LINE dfs2 ( v , child , u ) NEW_LINE DEDENT DEDENT def printHeights ( v , n ) : NEW_LINE INDENT global inn , out NEW_LINE dfs1 ( v , 1 , 0 ) NEW_LINE dfs2 ( v , 1 , 0 ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT print ( " The ▁ maximum ▁ height ▁ when ▁ node " , i , " is ▁ considered ▁ as ▁ root ▁ is " , max ( inn [ i ] , out [ i ] ) ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 11 NEW_LINE v = [ [ ] for i in range ( n + 1 ) ] NEW_LINE v [ 1 ] . append ( 2 ) NEW_LINE v [ 2 ] . append ( 1 ) NEW_LINE v [ 1 ] . append ( 3 ) NEW_LINE v [ 3 ] . append ( 1 ) NEW_LINE v [ 1 ] . append ( 4 ) NEW_LINE v [ 4 ] . append ( 1 ) NEW_LINE v [ 2 ] . append ( 5 ) NEW_LINE v [ 5 ] . append ( 2 ) NEW_LINE v [ 2 ] . append ( 6 ) NEW_LINE v [ 6 ] . append ( 2 ) NEW_LINE v [ 3 ] . append ( 7 ) NEW_LINE v [ 7 ] . append ( 3 ) NEW_LINE v [ 7 ] . append ( 10 ) NEW_LINE v [ 10 ] . append ( 7 ) NEW_LINE v [ 7 ] . append ( 11 ) NEW_LINE v [ 11 ] . append ( 7 ) NEW_LINE v [ 4 ] . append ( 8 ) NEW_LINE v [ 8 ] . append ( 4 ) NEW_LINE v [ 4 ] . append ( 9 ) NEW_LINE v [ 9 ] . append ( 4 ) NEW_LINE printHeights ( v , n ) NEW_LINE DEDENT