A tree \(T\) can be decomposed into paths only if every \(K\)-vertex subtree of \(T\) forms a path. Also, if \(T\) can be decomposed into paths, there always exists a \(K\)-vertex subtree.

Thus, \(T\) can be decomposed into paths if and only if one can remove all the vertices by repeatedly performing the following operation:

• choose an arbitrary \(K\)-vertex subtree, and remove it if it forms a path.

This operation can be done fast with tree DP. Regarding vertex \(1\) as the root, inspect the vertices from leaves, while managing the number of vertices \(s_v\) in the subtree \(T_v\) rooted at vertex \(v\). First, compute \(s_v\) as the sum of the values \(s\) for the children of \(v\), plus \(1\). Then, we divide into cases:

• If \(s_v < K\):
  • It always holds that \(v\neq 1\). As \(s_v < K\), any subtree containing \(v\) always contains entire \(T_v\) and the parent of \(v\). If \(c_v \geq 2\), then the degree of \(v\) is \(3\) or greater, so it can never form a path. Thus, if \(c_v \geq 2\), print No and terminate the program.
• If \(s_v > K\):
  • There is no \(K\)-vertex subtree in \(T_v\), so one cannot extract a path from \(T_v\). Thus, print No and terminate the program.
• If \(s_v = K\):
  • \(T_v\) must form a path. If \(c_v \geq 3\), then this is not a path; print No and terminate the program. If \(c_v \leq 2\), then this subtree forms a path. Let \(s_v \leftarrow 0\) to remove this subtree.

The time complexity is \(O(NK)\).

Sample code (Python)