Maximum product of two non | Returns maximum length path in subtree rooted at u after removing edge connecting u and v ; To find lengths of first and second maximum in subtrees . currMax is to store overall maximum . ; loop through all neighbors of u ; if neighbor is v , then skip it ; call recursively with current neighbor as root ; get max from one side and update ; store total length by adding max and second max ; update current max by adding 1 , i . e . current node is included ; method returns maximum product of length of two non - intersecting paths ; one by one removing all edges and calling dfs on both subtrees ; calling dfs on subtree rooted at g [ i ] [ j ] , excluding edge from g [ i ] [ j ] to i . ; calling dfs on subtree rooted at i , edge from i to g [ i ] [ j ] ; Utility function to add an undirected edge ( u , v ) ; Driver code ; there are N edges , so + 1 for nodes and + 1 for 1 - based indexing
def dfs ( g , curMax , u , v ) : NEW_LINE INDENT max1 = 0 NEW_LINE max2 = 0 NEW_LINE total = 0 NEW_LINE for i in range ( len ( g [ u ] ) ) : NEW_LINE INDENT if ( g [ u ] [ i ] == v ) : NEW_LINE INDENT continue NEW_LINE DEDENT total = max ( total , dfs ( g , curMax , g [ u ] [ i ] , u ) ) NEW_LINE if ( curMax [ 0 ] > max1 ) : NEW_LINE INDENT max2 = max1 NEW_LINE max1 = curMax [ 0 ] NEW_LINE DEDENT else : NEW_LINE INDENT max2 = max ( max2 , curMax [ 0 ] ) NEW_LINE DEDENT DEDENT total = max ( total , max1 + max2 ) NEW_LINE curMax [ 0 ] = max1 + 1 NEW_LINE return total NEW_LINE DEDENT def maxProductOfTwoPaths ( g , N ) : NEW_LINE INDENT res = - 999999999999 NEW_LINE path1 , path2 = None , None NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( len ( g [ i ] ) ) : NEW_LINE INDENT curMax = [ 0 ] NEW_LINE path1 = dfs ( g , curMax , g [ i ] [ j ] , i ) NEW_LINE curMax = [ 0 ] NEW_LINE path2 = dfs ( g , curMax , i , g [ i ] [ j ] ) NEW_LINE res = max ( res , path1 * path2 ) NEW_LINE DEDENT DEDENT return res NEW_LINE DEDENT def addEdge ( g , u , v ) : NEW_LINE INDENT g [ u ] . append ( v ) NEW_LINE g [ v ] . append ( u ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT edges = [ [ 1 , 8 ] , [ 2 , 6 ] , [ 3 , 1 ] , [ 5 , 3 ] , [ 7 , 8 ] , [ 8 , 4 ] , [ 8 , 6 ] ] NEW_LINE N = len ( edges ) NEW_LINE g = [ [ ] for i in range ( N + 2 ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT addEdge ( g , edges [ i ] [ 0 ] , edges [ i ] [ 1 ] ) NEW_LINE DEDENT print ( maxProductOfTwoPaths ( g , N ) ) NEW_LINE DEDENT