I was able to do a O(# of divisors of n-1 * N^2 solution), where for each K that is a divisor of n-1, I will run a dfs on the tree to see if we can partition the edges. My DFS is N^2, but I was able to get TC 5-8 correct. Everything else I got TLE. Any tips on how I can speed this up? I read the solution, and I cannot understand how they only use 1 dfs. What value of K do they use on that 1 iteration of dfs?
If you have a solution, it would be very helpful if you can post it here.