Maximum weighted edge in path between two nodes in an N | Python3 implementation to find the maximum weighted edge in the simple path between two nodes in N - ary Tree ; Depths of Nodes ; Parent at every 2 ^ i level ; Maximum node at every 2 ^ i level ; Graph that stores destinations and its weight ; Function to traverse the nodes using the Depth - First Search Traversal ; Condition to check if its equal to its parent then skip ; DFS Recursive Call ; Function to find the ansector ; Loop to set every 2 ^ i distance ; Loop to calculate for each node in the N - ary tree ; Storing maximum edge ; Swaping if node a is at more depth than node b because we will always take at more depth ; Difference between the depth of the two given nodes ; Changing Node B to its parent at 2 ^ i distance ; Subtracting distance by 2 ^ i ; Take both a , b to its lca and find maximum ; Loop to find the maximum 2 ^ ith parent the is different for both a and b ; Updating ans ; Changing value to its parent ; Function to compute the Least common Ansector ; Driver code ; Undirected tree ; Computing LCA
import math NEW_LINE N = 100005 ; NEW_LINE level = [ 0 for i in range ( N ) ] NEW_LINE LG = 20 ; NEW_LINE dp = [ [ 0 for j in range ( N ) ] for i in range ( LG ) ] NEW_LINE mx = [ [ 0 for j in range ( N ) ] for i in range ( LG ) ] NEW_LINE v = [ [ ] for i in range ( N ) ] NEW_LINE n = 0 NEW_LINE def dfs_lca ( a , par , lev ) : NEW_LINE INDENT dp [ 0 ] [ a ] = par ; NEW_LINE level [ a ] = lev ; NEW_LINE for i in v [ a ] : NEW_LINE INDENT if ( i [ 0 ] == par ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT mx [ 0 ] [ i [ 0 ] ] = i [ 1 ] ; NEW_LINE dfs_lca ( i [ 0 ] , a , lev + 1 ) ; NEW_LINE DEDENT DEDENT def find_ancestor ( ) : NEW_LINE INDENT for i in range ( 1 , 16 ) : NEW_LINE INDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ dp [ i - 1 ] [ j ] ] ; NEW_LINE mx [ i ] [ j ] = max ( mx [ i - 1 ] [ j ] , mx [ i - 1 ] [ dp [ i - 1 ] [ j ] ] ) ; NEW_LINE DEDENT DEDENT DEDENT def getMax ( a , b ) : NEW_LINE INDENT if ( level [ b ] < level [ a ] ) : NEW_LINE INDENT a , b = b , a NEW_LINE DEDENT ans = 0 ; NEW_LINE diff = level [ b ] - level [ a ] ; NEW_LINE while ( diff > 0 ) : NEW_LINE INDENT log = int ( math . log2 ( diff ) ) ; NEW_LINE ans = max ( ans , mx [ log ] [ b ] ) ; NEW_LINE b = dp [ log ] [ b ] ; NEW_LINE diff -= ( 1 << log ) ; NEW_LINE DEDENT while ( a != b ) : NEW_LINE INDENT i = int ( math . log2 ( level [ a ] ) ) ; NEW_LINE while ( i > 0 and dp [ i ] [ a ] == dp [ i ] [ b ] ) : NEW_LINE INDENT i -= 1 NEW_LINE DEDENT ans = max ( ans , mx [ i ] [ a ] ) ; NEW_LINE ans = max ( ans , mx [ i ] [ b ] ) ; NEW_LINE a = dp [ i ] [ a ] ; NEW_LINE b = dp [ i ] [ b ] ; NEW_LINE DEDENT return ans ; NEW_LINE DEDENT def compute_lca ( ) : NEW_LINE INDENT dfs_lca ( 1 , 0 , 0 ) ; NEW_LINE find_ancestor ( ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 ; NEW_LINE v [ 1 ] . append ( [ 2 , 2 ] ) ; NEW_LINE v [ 2 ] . append ( [ 1 , 2 ] ) ; NEW_LINE v [ 1 ] . append ( [ 3 , 5 ] ) ; NEW_LINE v [ 3 ] . append ( [ 1 , 5 ] ) ; NEW_LINE v [ 3 ] . append ( [ 4 , 3 ] ) ; NEW_LINE v [ 4 ] . append ( [ 3 , 4 ] ) ; NEW_LINE v [ 3 ] . append ( [ 5 , 1 ] ) ; NEW_LINE v [ 5 ] . append ( [ 3 , 1 ] ) ; NEW_LINE compute_lca ( ) ; NEW_LINE queries = [ [ 3 , 5 ] , [ 2 , 3 ] , [ 2 , 4 ] ] NEW_LINE q = 3 ; NEW_LINE for i in range ( q ) : NEW_LINE INDENT max_edge = getMax ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] ) ; NEW_LINE print ( max_edge ) NEW_LINE DEDENT DEDENT