How we can break 'n' into parts such that LCM of parts is maximum (number of parts should be greater than or equal to 2)? OR Find A1, A2, ..., Ak such that A1 + A2 + ... + Ak = n and LCM(A1, A2, ..., Ak) is maximum. Here 2 <= k <= n. Original Problem Link: http://acm.timus.ru/problem.aspx?space=1&num=1807

Need help! I tried to solve SPOJ QTREE4. I used centroid decomposition, but still getting TLE (time limit exceeded). In my code, a query is processed in O(log(n)^2). How can I improve complexity? Any suggestions. Here is my code.