Minimum time required to color all edges of a Tree | Stores the required answer ; Stores the graph ; Function to add edges ; Function to calculate the minimum time required to color all the edges of a tree ; Starting from time = 0 , for all the child edges ; If the edge is not visited yet . ; Time of coloring of the current edge ; If the parent edge has been colored at the same time ; Update the maximum time ; Recursively call the function to its child node ; Driver Code ; Function call ; Finally , print the answer
ans = 0 NEW_LINE edges = [ [ ] for i in range ( 100000 ) ] NEW_LINE def Add_edge ( u , v ) : NEW_LINE INDENT global edges NEW_LINE edges [ u ] . append ( v ) NEW_LINE edges [ v ] . append ( u ) NEW_LINE DEDENT def minTimeToColor ( node , parent , arrival_time ) : NEW_LINE INDENT global ans NEW_LINE current_time = 0 NEW_LINE for x in edges [ node ] : NEW_LINE INDENT if ( x != parent ) : NEW_LINE INDENT current_time += 1 NEW_LINE if ( current_time == arrival_time ) : NEW_LINE INDENT current_time += 1 NEW_LINE DEDENT ans = max ( ans , current_time ) NEW_LINE minTimeToColor ( x , node , current_time ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ [ 1 , 2 ] , [ 2 , 3 ] , [ 3 , 4 ] ] NEW_LINE for i in A : NEW_LINE INDENT Add_edge ( i [ 0 ] , i [ 1 ] ) NEW_LINE DEDENT minTimeToColor ( 1 , - 1 , 0 ) NEW_LINE print ( ans ) NEW_LINE DEDENT