Product of minimum edge weight between all pairs of a Tree | Python3 implementation of the approach ; Function to return ( x ^ y ) mod p ; Declaring size array globally ; Initializing DSU data structure ; Function to find the root of ith node in the disjoint set ; Weighted union using Path Compression ; size of set A is small than size of set B ; size of set B is small than size of set A ; Function to add an edge in the tree ; Build the tree ; Function to return the required product ; Sorting the edges with respect to its weight ; Start iterating in decreasing order of weight ; Determine Current edge values ; Calculate root of each node and size of each set ; Using the formula ; Calculating final result ; Weighted union using Path Compression ; Driver Code
mod = 1000000007 NEW_LINE def power ( x : int , y : int , p : int ) -> int : NEW_LINE INDENT res = 1 NEW_LINE x %= p NEW_LINE while y > 0 : NEW_LINE INDENT if y & 1 : NEW_LINE INDENT res = ( res * x ) % p NEW_LINE DEDENT y = y // 2 NEW_LINE x = ( x * x ) % p NEW_LINE DEDENT return res NEW_LINE DEDENT size = [ 0 ] * 300005 NEW_LINE freq = [ 0 ] * 300004 NEW_LINE edges = [ ] NEW_LINE def initialize ( arr : list , N : int ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT arr [ i ] = i NEW_LINE size [ i ] = 1 NEW_LINE DEDENT DEDENT def root ( arr : list , i : int ) -> int : NEW_LINE INDENT while arr [ i ] != i : NEW_LINE INDENT i = arr [ i ] NEW_LINE DEDENT return i NEW_LINE DEDENT def weighted_union ( arr : list , size : list , A : int , B : int ) : NEW_LINE INDENT root_A = root ( arr , A ) NEW_LINE root_B = root ( arr , B ) NEW_LINE if size [ root_A ] < size [ root_B ] : NEW_LINE INDENT arr [ root_A ] = arr [ root_B ] NEW_LINE size [ root_B ] += size [ root_A ] NEW_LINE DEDENT else : NEW_LINE INDENT arr [ root_B ] = arr [ root_A ] NEW_LINE size [ root_A ] += size [ root_B ] NEW_LINE DEDENT DEDENT def AddEdge ( a : int , b : int , w : int ) : NEW_LINE INDENT edges . append ( ( w , ( a , b ) ) ) NEW_LINE DEDENT def makeTree ( ) : NEW_LINE INDENT AddEdge ( 1 , 2 , 1 ) NEW_LINE AddEdge ( 1 , 3 , 3 ) NEW_LINE AddEdge ( 3 , 4 , 2 ) NEW_LINE DEDENT def minProduct ( ) -> int : NEW_LINE INDENT result = 1 NEW_LINE edges . sort ( key = lambda a : a [ 0 ] ) NEW_LINE for i in range ( len ( edges ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT curr_weight = edges [ i ] [ 0 ] NEW_LINE node1 = edges [ i ] [ 1 ] [ 0 ] NEW_LINE node2 = edges [ i ] [ 1 ] [ 1 ] NEW_LINE root1 = root ( freq , node1 ) NEW_LINE set1_size = size [ root1 ] NEW_LINE root2 = root ( freq , node2 ) NEW_LINE set2_size = size [ root2 ] NEW_LINE prod = set1_size * set2_size NEW_LINE product = power ( curr_weight , prod , mod ) NEW_LINE result = ( ( result % mod ) * ( product % mod ) ) % mod NEW_LINE weighted_union ( freq , size , node1 , node2 ) NEW_LINE DEDENT return result % mod NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 4 NEW_LINE initialize ( freq , n ) NEW_LINE makeTree ( ) NEW_LINE print ( minProduct ( ) ) NEW_LINE DEDENT