Farthest distance of a Node from each Node of a Tree | Python3 program to implement the above approach ; Adjacency List to store the graph ; Stores the height of each node ; Stores the maximum distance of a node from its ancestors ; Function to add edge between two vertices ; Insert edge from u to v ; Insert edge from v to u ; Function to calculate height of each Node ; Iterate in the adjacency list of the current node ; Dfs for child node ; Calculate height of nodes ; Increase height ; Function to calculate the maximum distance of a node from its ancestor ; Iterate in the adjacency list of the current node ; Find two children with maximum heights ; Calculate the maximum distance with ancestor for every node ; Calculating for children ; Driver Code ; Calculate height of nodes of the tree ; Calculate the maximum distance with ancestors ; Print the maximum of the two distances from each node
maxN = 100001 NEW_LINE adj = [ [ ] for i in range ( maxN ) ] NEW_LINE height = [ 0 for i in range ( maxN ) ] NEW_LINE dist = [ 0 for i in range ( maxN ) ] NEW_LINE def addEdge ( u , v ) : NEW_LINE INDENT adj [ u ] . append ( v ) NEW_LINE adj [ v ] . append ( u ) NEW_LINE DEDENT def dfs1 ( cur , par ) : NEW_LINE INDENT for u in adj [ cur ] : NEW_LINE INDENT if ( u != par ) : NEW_LINE INDENT dfs1 ( u , cur ) NEW_LINE height [ cur ] = max ( height [ cur ] , height [ u ] ) NEW_LINE DEDENT DEDENT height [ cur ] += 1 NEW_LINE DEDENT def dfs2 ( cur , par ) : NEW_LINE INDENT max1 = 0 NEW_LINE max2 = 0 NEW_LINE for u in adj [ cur ] : NEW_LINE INDENT if ( u != par ) : NEW_LINE INDENT if ( height [ u ] >= max1 ) : NEW_LINE INDENT max2 = max1 NEW_LINE max1 = height [ u ] NEW_LINE DEDENT elif ( height [ u ] > max2 ) : NEW_LINE INDENT max2 = height [ u ] NEW_LINE DEDENT DEDENT DEDENT sum = 0 NEW_LINE for u in adj [ cur ] : NEW_LINE INDENT if ( u != par ) : NEW_LINE INDENT sum = ( max2 if ( max1 == height [ u ] ) else max1 ) NEW_LINE if ( max1 == height [ u ] ) : NEW_LINE INDENT dist [ u ] = 1 + max ( 1 + max2 , dist [ cur ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dist [ u ] = 1 + max ( 1 + max1 , dist [ cur ] ) NEW_LINE DEDENT dfs2 ( u , cur ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 6 NEW_LINE addEdge ( 1 , 2 ) NEW_LINE addEdge ( 2 , 3 ) NEW_LINE addEdge ( 2 , 4 ) NEW_LINE addEdge ( 2 , 5 ) NEW_LINE addEdge ( 5 , 6 ) NEW_LINE dfs1 ( 1 , 0 ) NEW_LINE dfs2 ( 1 , 0 ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT print ( max ( dist [ i ] , height [ i ] ) - 1 , end = ' ▁ ' ) NEW_LINE DEDENT DEDENT