Lets see the problem as a graph problem (However just for understanding, no DFS or BFS 
)
First of all we will calculate answers for each power base and then would
multiply for answers for all powers, to get the final solution:
Here in my graph , ith index of array represents node ‘i’.
Lets solve the problem for power base p.
Lets say in the queries, A is connected to B and C with lcm’s being,
x and y resp. then max value at node A can be min(x,y) always.
(Lets say x was min, then if we give x+1 as node value, then the lcm
between A and B would exceed the given lcm would be >x, not valid.)
Now if we go through queries,
we will have an array (a) with max values of each node stored.
Let say arr is like = (a1, a2, a3, a4).
If no restrictions were there, then our answer would have been
Total arrays = (1+a1)(1+a2)(1+a3)…
Since allowed values for each is [0,ai]
But now there are restrictions of lcm between 2 nodes.
Now lets say if A and B was connected with lcm between them for
power p be ‘c’. Then if max value of both A and B is less than ‘c’
then we can never achieve that LCM. Thus if it happens in the graph
for any edge, our answer would be 0.
Lets say one of them is >=c (can always be at max c (Think! ;))
Then, we have to give one node a value of c and other node
can take whatsoever is wants , since their lcm would be c.
Here in the product = (1+a1)(1+a2)(1+a3)…
We are actually multiplying each possible value of node with others.
But this is not possible in case when edges is there bw nodes(both being less than c would mean invalid combination.)
, thus we would remove those terms in which any two nodes is
connected by an edge
For example
The graph was 1--------2
With lcm for power p being 3, and a1=3 and a2=3.
The possible values of array are :
0,3 ; 1,3 ; 2,3 ; 3,0 ; 3,1 ; 3,2 ; 3,3 = 1+3+3 = 1+a1+a2
( we deleted the term a1*a2 since there was an edge between 1 and 2).
Thus by following this algorithm, we find answers for each power
and then would multiply each other and get the answer.
(Beware of self edges-> say node a has self edge, then all the terms
with a gets deleted).
Overall Time Complexity → O(n^4)
My solution → https://www.codechef.com/viewsolution/35531057
.