Solve it for each prime separately. A number in the range 10000 has atmost 6 distinct prime factors. Consider all the primes that are part of atleast one value in the tree or atleast one k. For each of those primes, repeat the following:

When you update the value of the node, assign the respective power of that prime in the new value to the node. To check if the product of values along the path is divisible by k, find the power p of that prime in k and then it is equivalent to checking sum of values along the path is >= p.

For example, let's consider the prime 2. If we are asked to update the value of a node by 288, we find highest power of 2 in 288 which is 5, and add 5 to that node. Now we are asked to check if some path is divisible by 720. 720 = 2^4 * 3^2 * 5. The highest power of 2 in 720 is 4 so we check if sum along that path is atleast 4. The product will be divisible by 720 iff path sum (when processing 2) is >= 4, path sum (when processing 3) is >= 2 and path sum (when processing 5) is >= 1.

I am writer for this problem. Ok, so I will try and explain . First of all reading this blog should be useful. Please learn how to calculate path sum from this blog.

Now, note that a number K / A[i] / Y will have at max 6 distinct prime factors. If u can know for each of these primes their count that lies on the path from u to v, each query can be answered easily.

Finding the count of each prime online will require O(Z * N) memory, where Z is the number of primes  ≤ 200, 000. We cannot afford this.

So, we need to find some way to process the queries offline . But wait, we need to support updates too. How ?

Now, we will first break each update and query into its distinct prime factors of its (A[i] / Y / K), and then process these updates for each of them individually.

I.E. u can create a list of events for each prime, where each of these events may be an update/query in the order in which they appear in the input. You can maintain the count of a prime correctly for answering each of the queries for which you need its count.

For updates, we may need to dynamically update the path sum, we can use a fenwick tree for the purpose. Now, after you finish processing all the events for a particular prime, you can move onto the next one. Before this, you need to clear the fenwick tree.

u can solve it with HLD easily >>