# QMM - Editorial

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).