木 \(T\) がパスに分解できるためには，\(T\) の頂点数 \(K\) の部分木はパスになっている必要があります．また，\(T\) がパスに分解できるならば，頂点数 \(K\) の部分木が必ず存在します．

このことから，\(T\) をパスに分解することができる必要十分条件は，以下の操作を繰り返してすべての頂点を取り除くことができることです．

• 頂点数 \(K\) の部分木を任意に選び，それがパスであるならば，その部分木を取り除く

以上の操作は，木 DP によって高速に実行できます．頂点 \(1\) を根として，葉に近い頂点から順番に見ていって，各頂点 \(v\) を根とする部分木 \(T_v\) の頂点数 \(s_v\) を管理していきます．まず，\(s_v\) を「\(v\) の子についての \(s\) の総和 \(+1\)」として計算します．次に，\(s_v\) と \(K\) の大小関係および \(v\) の子の数 \(c_v\) で場合分けを行います．

• \(s_v < K\) のとき
  • このとき必ず \(v\neq 1\) です．\(s_v < K\) なので，\(v\) を含む部分木は \(T_v\) 全体と \(v\) の親を含みます．もし \(c_v \geq 2\) ならば，この部分木において \(v\) の次数は \(3\) 以上となるので，パスとなりえません．よって，\(c_v \geq 2\) ならば No を出力して終了します．
• \(s_v > K\) のとき
  • \(T_v\) の中に，頂点数 \(K\) の部分木が存在しないので，\(T_v\) からパスを取り出すことはできません．よって，No を出力して終了します．
• \(s_v = K\) のとき
  • \(T_v\) はパスになっている必要があります．\(c_v \geq 3\) ならば，これはパスでないので，No を出力して終了します．\(c_v \leq 2\) ならば，この部分木はパスになります．\(s_v \leftarrow 0\) とすることによってこの部分木を取り除きます．

時間計算量は \(O(NK)\) です．

実装例 (Python)