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.
What value of K do they use on that 1 iteration of dfs?
They don’t use any particular value of K in dfs. It calculates for each node a, the subtree sizes of each its children (sub[t])and the rest of the tree (N - sub[a]).
Also, do you understand the explanation of the editorial or do you just not get the implementation?
I don’t really understand the explanation. What do they mean by “a function dfs(x) which will check whether it is possible to partition the subtree corresponding to vertex x into paths of length K” when we don’t know K? Since we are only running DFS once.
Explanation means that you have something like
int dfs(int node, int parent, int k) {
...
}
and then you call this for each factor of N - 1.
from the analysis:
Another is to write a checker that does not use recursion and is a constant factor faster, demonstrated below.
^^ implementation is not exactly same as the explanation.