Product of minimum edge weight between all pairs of a Tree | C ++ Implementation of above 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define mod  1000000007 NEW_LINE int power ( int x , unsigned int y , int p ) { int res = 1 ; x = x % p ; while ( y > 0 ) { if ( y & 1 ) res = ( res * x ) % p ; y = y >> 1 ; x = ( x * x ) % p ; } return res ; } int size [ 300005 ] ; int freq [ 300004 ] ; vector < pair < int , pair < int , int > > > edges ; void initialize ( int Arr [ ] , int N ) { for ( int i = 0 ; i < N ; i ++ ) { Arr [ i ] = i ; size [ i ] = 1 ; } } int root ( int Arr [ ] , int i ) { while ( Arr [ i ] != i ) { i = Arr [ i ] ; } return i ; } void weighted_union ( int Arr [ ] , int size [ ] , int A , int B ) { int root_A = root ( Arr , A ) ; int root_B = root ( Arr , B ) ; if ( size [ root_A ] < size [ root_B ] ) { Arr [ root_A ] = Arr [ root_B ] ; size [ root_B ] += size [ root_A ] ; } else { Arr [ root_B ] = Arr [ root_A ] ; size [ root_A ] += size [ root_B ] ; } } void AddEdge ( int a , int b , int w ) { edges . push_back ( { w , { a , b } } ) ; } void MakeTree ( ) { AddEdge ( 1 , 2 , 1 ) ; AddEdge ( 1 , 3 , 3 ) ; AddEdge ( 3 , 4 , 2 ) ; } int MinProduct ( ) { int result = 1 ; sort ( edges . begin ( ) , edges . end ( ) ) ; for ( int i = edges . size ( ) - 1 ; i >= 0 ; i -- ) { int curr_weight = edges [ i ] . first ; int Node1 = edges [ i ] . second . first ; int Node2 = edges [ i ] . second . second ; int Root1 = root ( freq , Node1 ) ; int Set1_size = size [ Root1 ] ; int Root2 = root ( freq , Node2 ) ; int Set2_size = size [ Root2 ] ; int prod = Set1_size * Set2_size ; int Product = power ( curr_weight , prod , mod ) ; result = ( ( result % mod ) * ( Product % mod ) ) % mod ; weighted_union ( freq , size , Node1 , Node2 ) ; } return result % mod ; } int main ( ) { int n = 4 ; initialize ( freq , n ) ; MakeTree ( ) ; cout << MinProduct ( ) ; }