 # Delegation Gold

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?

1 Like

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.