Given a tree with N vertices and N-1 Edges. Let’s define a function F(a, b) which is equal to the minimum edge weight in the path between node a & b. The task is to calculate the product of all such F(a, b). Here a&b are unordered pairs and a!=b.
So, basically, we need to find the value of:
where 0<=i<j<=n-1.
where 0<=i<j<=n-1.In the input, we will be given the value of N and then N-1 lines follow. Each line contains 3 integers u, v, w denoting edge between node u and v and it’s weight w. Since the product will be very large, output it modulo 10^9+7.
Examples:
Input :
N = 4
1 2 1
1 3 3
4 3 2
Output : 12
Given tree is:
1
(1)/ \(3)
2 3
\(2)
4
We will calculate the minimum edge weight between all the pairs:
F(1, 2) = 1 F(2, 3) = 1
F(1, 3) = 3 F(2, 4) = 1
F(1, 4) = 2 F(3, 4) = 2
Product of all F(i, j) = 1*3*2*1*1*2 = 12 mod (10^9 +7) =12
Input :
N = 5
1 2 1
1 3 3
4 3 2
1 5 4
Output :
288
If we observe carefully then we will see that if there is a set of nodes in which minimum edge weight is w and if we add a node to this set that connects the node with the whole set by an edge of weight W such that W<w then path formed between recently added node to all nodes present in the set will have minimum weight W.
So, here we can apply Disjoint-Set Union concept to solve the problem.
First, sort the data structure according to decreasing weight. Initially assign all nodes as a single set. Now when we merge two sets then do the following:-
Product=(present weight)^(size of set1*size of set2).
We will multiply this product value for all edges of the tree.
Below is the implementation of the above approach:
C++
// C++ Implementation of above approach#include <bits/stdc++.h>using namespace std;#define mod 1000000007// Function to return (x^y) mod pint 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;}// Declaring size array globallyint size[300005];int freq[300004];vector<pair<int, pair<int, int> > > edges;// Initializing DSU data structurevoid initialize(int Arr[], int N){ for (int i = 0; i < N; i++) { Arr[i] = i; size[i] = 1; }}// Function to find the root of ith// node in the disjoint setint root(int Arr[], int i){ while (Arr[i] != i) { i = Arr[i]; } return i;}// Weighted union using Path Compressionvoid weighted_union(int Arr[], int size[], int A, int B){ int root_A = root(Arr, A); int root_B = root(Arr, B); // size of set A is small than size of set B if (size[root_A] < size[root_B]) { Arr[root_A] = Arr[root_B]; size[root_B] += size[root_A]; } // size of set B is small than size of set A else { Arr[root_B] = Arr[root_A]; size[root_A] += size[root_B]; }}// Function to add an edge in the treevoid AddEdge(int a, int b, int w){ edges.push_back({ w, { a, b } });}// Build the treevoid MakeTree(){ AddEdge(1, 2, 1); AddEdge(1, 3, 3); AddEdge(3, 4, 2);}// Function to return the required productint MinProduct(){ int result = 1; // Sorting the edges with respect to its weight sort(edges.begin(), edges.end()); // Start iterating in decreasing order of weight for (int i = edges.size() - 1; i >= 0; i--) { // Determine Current edge values int curr_weight = edges[i].first; int Node1 = edges[i].second.first; int Node2 = edges[i].second.second; // Calculate root of each node // and size of each set int Root1 = root(freq, Node1); int Set1_size = size[Root1]; int Root2 = root(freq, Node2); int Set2_size = size[Root2]; // Using the formula int prod = Set1_size * Set2_size; int Product = power(curr_weight, prod, mod); // Calculating final result result = ((result % mod) * (Product % mod)) % mod; // Weighted union using Path Compression weighted_union(freq, size, Node1, Node2); } return result % mod;}// Driver codeint main(){ int n = 4; initialize(freq, n); MakeTree(); cout << MinProduct();} |
Java
// Java Implementation of above approachimport java.util.ArrayList;import java.util.Collections;public class Product { // to store first vertex, second vertex and weight of // the edge static class Edge implements Comparable<Edge> { int first, second, weight; Edge(int x, int y, int w) { this.first = x; this.second = y; this.weight = w; } @Override public int compareTo(Edge edge) { return this.weight - edge.weight; } } static int mod = 1000000007; // Function to return (x^y) mod p static int power(int x, int y, int p) { int res = 1; x = x % p; while (y > 0) { if ((y & 1) == 1) res = (res * x) % p; y = y >> 1; x = (x * x) % p; } return res; } // Declaring size array globally static int size[] = new int[300005]; static int freq[] = new int[300004]; static ArrayList<Edge> edges = new ArrayList<Edge>(); // Initializing DSU data structure static void initialize(int Arr[], int N) { for (int i = 0; i < N; i++) { Arr[i] = i; size[i] = 1; } } // Function to find the root of ith // node in the disjoint set static int root(int Arr[], int i) { while (Arr[i] != i) { i = Arr[i]; } return i; } // Weighted union using Path Compression static void weighted_union(int Arr[], int size[], int A, int B) { int root_A = root(Arr, A); int root_B = root(Arr, B); // size of set A is small than size of set B if (size[root_A] < size[root_B]) { Arr[root_A] = Arr[root_B]; size[root_B] += size[root_A]; } // size of set B is small than size of set A else { Arr[root_B] = Arr[root_A]; size[root_A] += size[root_B]; } } // Function to add an edge in the tree static void AddEdge(int a, int b, int w) { edges.add(new Edge(a, b, w)); } // Build the tree static void MakeTree() { AddEdge(1, 2, 1); AddEdge(1, 3, 3); AddEdge(3, 4, 2); } // Function to return the required product static int MinProduct() { int result = 1; // Sorting the edges with respect to its weight // ascending order Collections.sort(edges); // Start iterating in decreasing order of weight for (int i = edges.size() - 1; i >= 0; i--) { // Determine Current edge values int curr_weight = edges.get(i).weight; int Node1 = edges.get(i).first; int Node2 = edges.get(i).second; // Calculate root of each node // and size of each set int Root1 = root(freq, Node1); int Set1_size = size[Root1]; int Root2 = root(freq, Node2); int Set2_size = size[Root2]; // Using the formula int prod = Set1_size * Set2_size; int Product = power(curr_weight, prod, mod); // Calculating final result result = ((result % mod) * (Product % mod)) % mod; // Weighted union using Path Compression weighted_union(freq, size, Node1, Node2); } return result % mod; } // Driver code public static void main(String[] args) { int n = 4; initialize(freq, n); MakeTree(); System.out.println(MinProduct()); }}// This code is contributed by jainlovely450 |
Python3
# Python3 implementation of the approachmod = 1000000007# Function to return (x^y) mod pdef power(x: int, y: int, p: int) -> int: res = 1 x %= p while y > 0: if y & 1: res = (res * x) % p y = y // 2 x = (x * x) % p return res# Declaring size array globallysize = [0] * 300005freq = [0] * 300004edges = []# Initializing DSU data structuredef initialize(arr: list, N: int): for i in range(N): arr[i] = i size[i] = 1# Function to find the root of ith# node in the disjoint setdef root(arr: list, i: int) -> int: while arr[i] != i: i = arr[i] return i# Weighted union using Path Compressiondef weighted_union(arr: list, size: list, A: int, B: int): root_A = root(arr, A) root_B = root(arr, B) # size of set A is small than size of set B if size[root_A] < size[root_B]: arr[root_A] = arr[root_B] size[root_B] += size[root_A] # size of set B is small than size of set A else: arr[root_B] = arr[root_A] size[root_A] += size[root_B]# Function to add an edge in the treedef AddEdge(a: int, b: int, w: int): edges.append((w, (a, b)))# Build the treedef makeTree(): AddEdge(1, 2, 1) AddEdge(1, 3, 3) AddEdge(3, 4, 2)# Function to return the required productdef minProduct() -> int: result = 1 # Sorting the edges with respect to its weight edges.sort(key = lambda a: a[0]) # Start iterating in decreasing order of weight for i in range(len(edges) - 1, -1, -1): # Determine Current edge values curr_weight = edges[i][0] node1 = edges[i][1][0] node2 = edges[i][1][1] # Calculate root of each node # and size of each set root1 = root(freq, node1) set1_size = size[root1] root2 = root(freq, node2) set2_size = size[root2] # Using the formula prod = set1_size * set2_size product = power(curr_weight, prod, mod) # Calculating final result result = ((result % mod) * (product % mod)) % mod # Weighted union using Path Compression weighted_union(freq, size, node1, node2) return result % mod# Driver Codeif __name__ == "__main__": # Number of nodes and edges n = 4 initialize(freq, n) makeTree() print(minProduct())# This code is contributed by# sanjeev2552 |
Javascript
<script>// JavaScript implementation of the approachconst mod = 1000000007// Function to return (x^y) mod pfunction power(x, y, p){ let res = 1 x %= p while(y > 0){ if(y & 1) res = (res * x) % p y = Math.floor(y / 2) x = (x * x) % p } return res}// Declaring size array globallylet size = new Array(300005).fill(0)let freq = new Array(300004).fill(0)let edges = []// Initializing DSU data structurefunction initialize(arr, N){ for(let i=0;i<N;i++){ arr[i] = i size[i] = 1 }}// Function to find the root of ith// node in the disjoint setfunction root(arr, i){ while(arr[i] != i) i = arr[i] return i}// Weighted union using Path Compressionfunction weighted_union(arr, size, A, B){ let root_A = root(arr, A) let root_B = root(arr, B) // size of set A is small than size of set B if(size[root_A] < size[root_B]){ arr[root_A] = arr[root_B] size[root_B] += size[root_A] } // size of set B is small than size of set A else{ arr[root_B] = arr[root_A] size[root_A] += size[root_B] }}// Function to add an edge in the treefunction AddEdge(a, b, w){ edges.push([w, [a, b]])}// Build the treefunction makeTree(){ AddEdge(1, 2, 1) AddEdge(1, 3, 3) AddEdge(3, 4, 2)}// Function to return the required productfunction minProduct(){ let result = 1 // Sorting the edges with respect to its weight edges.sort((a,b)=>a[0]-b[0]) // Start iterating in decreasing order of weight for(let i=edges.length - 1;i>=0;i--){ // Determine Current edge values let curr_weight = edges[i][0] let node1 = edges[i][1][0] let node2 = edges[i][1][1] // Calculate root of each node // and size of each set let root1 = root(freq, node1) let set1_size = size[root1] let root2 = root(freq, node2) let set2_size = size[root2] // Using the formula let prod = set1_size * set2_size let product = power(curr_weight, prod, mod) // Calculating final result result = ((result % mod) * (product % mod)) % mod // Weighted union using Path Compression weighted_union(freq, size, node1, node2) } return result % mod}// Driver Code// Number of nodes and edgeslet n = 4initialize(freq, n)makeTree()document.write(minProduct(),"</br>")// This code is contributed by shinjanpatra</script> |
C#
// C# code for the above approachusing System;using System.Collections.Generic;namespace MinimumProductSpanningTree {// to store first vertex, second vertex and weight of// the edgeclass Edge : IComparable<Edge> { public int First { get; set; } public int Second { get; set; } public int Weight { get; set; } public Edge(int x, int y, int w) { First = x; Second = y; Weight = w; } public int CompareTo(Edge edge) { return Weight - edge.Weight; }}class Program { static readonly int Mod = 1000000007; // Declaring size array globally static readonly int[] Size = new int[300005]; static readonly int[] Freq = new int[300004]; static readonly List<Edge> Edges = new List<Edge>(); // Function to Inialize DSU static void Initialize(int[] arr, int n) { for (int i = 0; i < n; i++) { arr[i] = i; Size[i] = 1; } } // Function to find the root of ith // node in the disjoint set static int Root(int[] arr, int i) { while (arr[i] != i) { i = arr[i]; } return i; } static void WeightedUnion(int[] arr, int[] size, int a, int b) { int rootA = Root(arr, a); int rootB = Root(arr, b); if (size[rootA] < size[rootB]) { arr[rootA] = arr[rootB]; size[rootB] += size[rootA]; } else { arr[rootB] = arr[rootA]; size[rootA] += size[rootB]; } } static void AddEdge(int a, int b, int w) { Edges.Add(new Edge(a, b, w)); } // Build the tree static void MakeTree() { AddEdge(1, 2, 1); AddEdge(1, 3, 3); AddEdge(3, 4, 2); } // Function to return the required product static int MinProduct() { int result = 1; // Sorting the edges with respect to its weight // ascending order Edges.Sort(); // Start iterating in decreasing order of weight for (int i = Edges.Count - 1; i >= 0; i--) { // Determine Current edge values int currWeight = Edges[i].Weight; int node1 = Edges[i].First; int node2 = Edges[i].Second; // Calculate root of each node // and size of each set int root1 = Root(Freq, node1); int set1Size = Size[root1]; int root2 = Root(Freq, node2); int set2Size = Size[root2]; // Using the formula int prod = set1Size * set2Size; int product = Power(currWeight, prod, Mod); // Calculating final result result = (result * product) % Mod; // Weighted union using Path Compression WeightedUnion(Freq, Size, node1, node2); } return result; } // Function to return (x^y) mod p static int Power(int x, int y, int p) { int res = 1; x = x % p; while (y > 0) { if ((y & 1) == 1) { res = (res * x) % p; } y = y >> 1; x = (x * x) % p; } return res; } // Driver code static void Main(string[] args) { Initialize(Freq, 300004); MakeTree(); Console.WriteLine(MinProduct()); }}}// This code is contributed by Potta Lokesh |
Output:
12
Time Complexity : O(N*logN)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
