I was solving this interesting [number-theory + trees problem](https://mirror.codeforces.com/contest/842/problem/C). ↵
And I came up with an $O(n\sqrt{n})$ solution where $n \leq 200000$. ↵
↵
My idea is that the answer for every node will either be a factor of the root or be a factor of the number itself, and only these about $2 \sqrt{n}$ values need to be tested.↵
↵
However, [this submission am getting TLE with this idea](https://mirror.codeforces.com/contest/842/submission/46672103). The solution in the editorial is a slight optimization of my idea -(a) either the answer is a factor of the root (because root is NOT marked as 0) ↵
(b) or it's the GCD of all the ancestors except the root (because the root IS marked as $0$. ↵
↵
This has the complexity of $O(n * k)$ where $k = $ number of factors of the root value, and $k = O(\sqrt{n}). Thus the editorial solution and my solution have the same (theoretical) complexity. ↵
↵
Could you suggest was that are C++ optimizations that I could use to improve my solution and avoid the TLE even though I am testing out both factors of root and factors of the node? I did try to cache the values of the root and the node, but that leads to a stack overflow. ↵
↵
(a) either the answer is a factor of the root (because root is NOT marked as $0$) ↵
(b) or it's the GCD of all the ancestors except the root (because the root IS marked as $0$). ↵
↵
This has the complexity of $O(n * k)$ where $k = $ number of factors of the root value, and $k = O(\sqrt{n})$. Thus the editorial solution and my solution have the same (theoretical) complexity. ↵
↵
Could you suggest was that are __C++ implementation optimizations__ that I could use to improve my solution and avoid the TLE even though I am testing out both factors of root and factors of the node? I did try to [cache the values of the root and the node, but that leads to a stack overflow](https://mirror.codeforces.com/contest/842/submission/46671618).↵
↵
I am not looking for the obvious optimizations of implementing the editorial solution.
And I came up with an $O(n\sqrt{n})$ solution where $n \leq 200000$. ↵
↵
My idea is that the answer for every node will either be a factor of the root or be a factor of the number itself, and only these about $2 \sqrt{n}$ values need to be tested.↵
↵
However, [this submission am getting TLE with this idea](https://mirror.codeforces.com/contest/842/submission/46672103). The solution in the editorial is a slight optimization of my idea -
(b) or it's the GCD of all the ancestors except the root (because the root IS marked as $0$. ↵
↵
This has the complexity of $O(n * k)$ where $k = $ number of factors of the root value, and $k = O(\sqrt{n}). Thus the editorial solution and my solution have the same (theoretical) complexity. ↵
↵
Could you suggest was that are C++ optimizations that I could use to improve my solution and avoid the TLE even though I am testing out both factors of root and factors of the node? I did try to cache the values of the root and the node, but that leads to a stack overflow. ↵
(a) either the answer is a factor of the root (because root is NOT marked as $0$) ↵
(b) or it's the GCD of all the ancestors except the root (because the root IS marked as $0$). ↵
↵
This has the complexity of $O(n * k)$ where $k = $ number of factors of the root value, and $k = O(\sqrt{n})$. Thus the editorial solution and my solution have the same (theoretical) complexity. ↵
↵
Could you suggest was that are __C++ implementation optimizations__ that I could use to improve my solution and avoid the TLE even though I am testing out both factors of root and factors of the node? I did try to [cache the values of the root and the node, but that leads to a stack overflow](https://mirror.codeforces.com/contest/842/submission/46671618).↵
↵
I am not looking for the obvious optimizations of implementing the editorial solution.
