By aditya305, history, 3 months ago, ,

Problem. I checked various solutions. I could see DSU and Dynamic programming in most of them. Any hint or full solution would be helpful.

• +1

 » 3 months ago, # | ← Rev. 2 →   +11 Here's a very similar problem on an Educational round. I would recommend understanding the solution based on centroid decomposition (even though it isn't strictly required here), since it is much more general and can solve a variety of problems of this kind, i.e., obtaining information about all paths in a tree.
•  » » 3 months ago, # ^ |   +20 It's actually the SAME problem. Shame on the codechef author :(
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +13 Funnily enough, I actually ACed the Educational Round problem before the CodeChef contest, but kept TLEing on the CodeChef version of the problem (I never thought to check my old CF submissions during contest :( ). The decrease of the TL from 4.5 seconds to 3.0 seconds in addition to there being 10 testcases v.s. 1 testcase in an input is highly annoying, as it required several relatively hacky optimizations (e.g. precomputing the GCD >= 1 case) to make a modification of the Educational Round solution pass (and still doesn't make it qualify as a unique problem)./endsaltIs there a better complexity solution that CodeChef expected?
 » 3 months ago, # |   +5 $n = \sum_{d|n} \phi(d)$