Statement
You are given a rooted tree with N nodes (numbered 1 through N); node 1 is the root. For each valid i, the ith node has a value v_{i} and another parameter m_{i}.
A leaf is a node without sons. Let’s denote the number of leaf nodes in the tree by L and their numbers by l_{1}, l_{2},… l_{L1} ,l_{L} , in increasing order. Then, for each valid i, let’s define the answer for the leaf l_{i} in the following way:
 Consider the path from the root to l_{i}. For each node on this path (including the root and this leaf), choose a nonnegative integer and multiply the value of this node by it.
 Sum up the resulting values of all nodes on this path.
 The answer a_{i} for this leaf is defined as the maximum possible remainder of this sum modulo m_{li} .
Find the answers for all leaves.
Constraints
 1 ≤ T ≤ 8
 2 ≤ N ≤ 10^{5}
 1 ≤ x , y ≤ N
 1 ≤ v _{i} ≤ 10^{18} for each valid i
 1 ≤ m_{i} ≤ 10^{18} for each valid i
 the graph described on the input is a tree
Soln:

The very first idea is if in the worst case the height of the tree can be N here and every node can contain a value up to 10^{18} , So if we are going to add these the result of addition can be upto 10^{23} , then probably we shouldn’t add these.

Again we have to calculate modulo then we know that 
m % n = we can make it upto ( n1 ) by multiplying some number but not always. if m and n are coprime or we can say if they have gcd equals to 1 then we can make it. but if their gcd's are not equal to 1 then the maximum value of m%n will be = ngcd(m,n) try this it is a nice observation.

So why not we try to make the gcd of every element , that occurs in the path from root to the leaf node ,equals to 1. Then we have to take the cumulative gcd of the element occurring in that path.

How do we get the path?

Now we can apply dfs from root node and store the cumulative gcd’s like this
void dfs(int node , int parent){
visited[node] = true;
cumulative_gcd[node] = gcd(value[node],cumulative_gcd[parent]);
for(auto neighbour : tree[node]){
if(visited[neighbour] == true)
dfs(neighbour,node);
}

Now at last we can collect all the leaf node (index ) and sort them in increasing order.

Then we’ll apply our gcd trick to get the answer for every leaf.
Any doubts or questions are Welcomed.
PS: This is my first editorial on CodeChef. Any suggestion are also welcomed
Happy Coding
Thank You CodeChef.