problem in brief:
problem link
you are given a Tree of nodes n(<=2e5). Each nodes has value x(<=2e5).
Let's denote the function g(x,y) as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex x to vertex y (including these two vertices).
For every integer from 1 to 2e5 you have to count the number of pairs (x,y)(1≤x≤y≤n) such that g(x,y) is equal to this number.
My idea:
As the number can be at most 2e5 so, the total number of divisors can be maximum 160.I just stored possible unique gcd for each node u where paths end at some nodes in subtree u. total numbers can be maximum 160 as well for each nodes. while traveling each node I calculated possible answers where paths start at some node in subtree u and ends at some nodes in subtree u. Finally when return back to parent node I cleared the memory of every childs to save memory.
Unfortunately, I got memory limit exceeded at test 100. but I have no idea why as I store values at only one node at a particular time.
Any suggestions will be appreciated.
Thanks.
Instead of vectors take array of pairs.
g[2e5][160][2] will easily cross memory limit.
Not the adjacency list. Especially, the ones inside the dfs function.