Let \(G\) be the graph/tree given in the input.

We may think of a BFS over a state-transition graph, where the states are denoted by a triple \((u, v, k)\) such that:

• \(\{u, v\}\) is an edge in \(G\) in either direction, meaning you just stepped through that edge and arrived at \(v\).
• \(k\) is an integer \(0 \le k < K\), representing the number of single steps taken modulo \(K\).

And that there are transitions from \((u, v, k)\) to \((v, w, (k + 1) \text{ mod }K)\), where:

• \(\{v, w\}\) is an edge in \(G\)
• \(w \ne u \vee k = 0\) [i.e. don’t “double back” on an edge unless we’ve just “landed” from a \(K\)-length jump]

The source state would be \((x, 1, 0)\) for any arbitrary \(\{x, 1\} \in G\), and the answer for each vertex \(v\) would be \(\min _u \text{dist}(u, v, 0) / K\).

However, this will exceed the time limit. This is because even though you have only \(O(NK)\) possible states, a vertex of \(G\) with degree \(d\) may be visited up to \(d \cdot K\) times, thus producing \(\Theta(d^2 K)\) transitions, taking \(\Theta(N^2K)\) time in the worst case.

To fix it, we only process transitions from equivalence classes \((*, v, k)\) up to twice each. This is because when we transition from \((u, v, k)\), we will then visit all \((v, w, (k + 1) \text{ mod }K)\) with the possible exception of \(w = u\). The second transition from \((*, v, k)\) would then be from a different edge and thus would definitely cover \(w = u\).

Thus, each vertex of \(G\) will only be transitioned from up to \(2K\) times, and thus the solution will run in \(O(NK)\), which should be fast enough to pass.