human
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"
How can the above be solved in Python?
assistant
#Here is code to maximum product of two non and the other steps required.
 def dfs ( g , curMax , u , v ) :
	max1 = 0
	max2 = 0
	total = 0
	for i in range ( len ( g [ u ] ) ) :
		if ( g [ u ] [ i ] == v ) :
			continue
		total = max ( total , dfs ( g , curMax , g [ u ] [ i ] , u ) )
		if ( curMax [ 0 ] > max1 ) :
			max2 = max1
			max1 = curMax [ 0 ]
		else :
			max2 = max ( max2 , curMax [ 0 ] )
	total = max ( total , max1 + max2 )
	curMax [ 0 ] = max1 + 1
	return total
def maxProductOfTwoPaths ( g , N ) :
	res = - 999999999999
	path1 , path2 = None , None
	for i in range ( N ) :
		for j in range ( len ( g [ i ] ) ) :
			curMax = [ 0 ]
			path1 = dfs ( g , curMax , g [ i ] [ j ] , i )
			curMax = [ 0 ]
			path2 = dfs ( g , curMax , i , g [ i ] [ j ] )
			res = max ( res , path1 * path2 )
	return res
def addEdge ( g , u , v ) :
	g [ u ] . append ( v )
	g [ v ] . append ( u )
if __name__ == ' _ _ main _ _ ' :
	edges = [ [ 1 , 8 ] , [ 2 , 6 ] , [ 3 , 1 ] , [ 5 , 3 ] , [ 7 , 8 ] , [ 8 , 4 ] , [ 8 , 6 ] ]
	N = len ( edges )
	g = [ [ ] for i in range ( N + 2 ) ]
	for i in range ( N ) :
		addEdge ( g , edges [ i ] [ 0 ] , edges [ i ] [ 1 ] )
	print ( maxProductOfTwoPaths ( g , N ) )