Auto comment: topic has been updated by coding_weeb (previous revision, new revision, compare).

Hint : If you have many continuous SEED queries, how will you solve it?

You can construct euler order of tree, so each rooted subtree can be mapped subarray of the order.

If you don't know, what is euler order of graph, there is small summary about it.

1. Run dfs from root;
2. Each time when you enter to new node — add it to the end of order;
3. Each time when you exit node — add it to the end of order;

Let's tin[v] is index of 'enter' v at the order and tout[v] is index of 'exit' v at the order. Then all vertices from T(v) are between tin[v] and tout[v] in order and no other vertices are there.

In converts queries:

• 'update value in node v' to 'update value at index tin[v]'
• 'product of all values in the subtree T(v)' to 'product of all values in the subarray tin[v]... tout[v]'

Segment tree or Fenwick tree can handle these queries easily in O(logN).

But for this problem product can be very-very large. Even number of divisors of product can be much more that 64-bit values.

So what we needed here is formula for number of divisors. Let X = p₁^a₁·p₂^a₂...·p_m^a_m, where p_i^a_i are powers of different primes, It can be shown that number of divisors of X is (a₁ + 1)·(a₂ + 1)...·(a_m + 1).

We can see that there is guaranteed that all prime divisors of values in problem are  ≤ 13, so there are only 6 different prime divisors could be: (2, 3, 5, 7, 11, 13).

Using this fact, you can solve this problem next way:

• for each possible prime divisor construct segment/fenwick tree for euler order of graph;
• each update increases powers of it's prime divisors at index, mapped for updated node;
• each query collect sums for each prime separately from segment, mapped to subtree, and multiplies them.