PROBLEM LINKS:
DIFFICULTY:
Easy
PREREQUISITES:
- Disjoint set union
- Sieve of Eratosthenes
PROBLEM:
Given an undirected connected graph with N nodes and
N-1 edges.Let xab be the maximum edge weight
in the path a to b and yab be the minimum edge weight in the
path a to b.
P is equal to product of xab for all a,b such
that 1 <= a, b <= N where xab and xba is considered
same.
Q is equal to product of yab for all a,b such
that 1 <= a, b <= N where yab and yba is considered
same.
Z is equal to the maximum power to which Q can be raised
that when P is divided by it the remainder is 0.
Output P(mod 109+7), Q(mod 109+7) and Z.
EXPLANATION :
In a vector store the pair of nodes with their respective edge weights.
To get product of maximum weight between all pairs with (a,b) and (b,a) counted
once sort the vector in increasing order of edge weights.
Loop and get value of r[find(node1)] and r[find(node2)] (which provides number of nodes connected directly and indirectly to node1 and node2 including themselves), update the answer as
ans*power(weight,r[find(node1)]*r[find(node2)] and
take union(node1,node2) for every vector index.
For minimum weight do the above thing with vector sorted in decreasing order of weights.
Get P and Q in form of prime factors raised to respective powers using sieve and calculate Z.
TIME COMPLEXITY:
O(nlogn).