The value of a node is the product of all the node in its subtree. So how do you update all the parent node when you update the child node ? The original problem is http://codeforces.com/gym/101466/problem/K.

# | User | Rating |
---|---|---|

1 | tourist | 3496 |

2 | Um_nik | 3337 |

3 | Petr | 3298 |

4 | W4yneb0t | 3218 |

5 | Radewoosh | 3216 |

6 | OO0OOO00O0OOO0O0…O | 3188 |

7 | Syloviaely | 3168 |

8 | izrak | 3109 |

9 | anta | 3106 |

10 | fateice | 3099 |

# | User | Contrib. |
---|---|---|

1 | tourist | 184 |

2 | rng_58 | 170 |

3 | csacademy | 165 |

4 | Petr | 158 |

5 | Swistakk | 154 |

6 | lewin | 149 |

7 | Errichto | 147 |

8 | matthew99 | 145 |

9 | Zlobober | 141 |

9 | adamant | 141 |

The value of a node is the product of all the node in its subtree. So how do you update all the parent node when you update the child node ? The original problem is http://codeforces.com/gym/101466/problem/K.

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/21/2018 18:16:01 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|

Auto comment: topic has been updated by i_love_phuong_loan (previous revision, new revision, compare).Hint : If you have many continuous

SEEDqueries, how will you solve it?Oh so I should handle it offline right

Keep a list of

SEEDqueries. For eachRANDquery, the answer is the product of currentT_{u}and every updates onu's children in this list.When the list reaches 300 updates, we'll update all the tree with the list in

O(n) and clear the list.This is not a nice way to solve this problem but i think it's easier to understand.

Thank you highly appreciate 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.

Let's

tin[v] is index of 'enter'vat the order andtout[v] is index of 'exit'vat the order. Then all vertices fromT(v) are betweentin[v] andtout[v] in order and no other vertices are there.In converts queries:

v' to 'update value at indextin[v]'T(v)' to 'product of all values in the subarraytin[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_{1}^{a1}·p_{2}^{a2}...·p_{m}^{am}, wherep_{i}^{ai}are powers of different primes, It can be shown that number of divisors ofXis (a_{1}+ 1)·(a_{2}+ 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:

Thank you that's very easy to understand.