Code Senso : Sardar & GCD ( Tree DP Problem) HELP!

I was trying to solve this problem in the contest today, this was some kind of DP on trees which can be solved using re-rooting type DP but I got another idea and I tried to implement it but unfortunately got TLE. I would like to ask the CODECHEF community to see through it once and see if anyone can help me with the time complexity of my solution.

Link to the problem : DLTNODE
Link to the solution : TLE :neutral_face:

Looks O(N^2) to me: consider the case where N is large and vertices 2,3,\dots N-1 are connected to vertex 1.

1 Like