各節点 \(i\) に対して多項式 \(f _ { i, 0 }, f _ { i, 1 }, f _ { i, 2 }\) を

• \([x^d]x_{i,0} \! \in \! \mathbb{N}\): 根を含まない \(d\) 本の disjoint なパスを書く場合の数
• \([x^d]x_{i,1} \! \in \! \mathbb{N}\): \(1 \! + \! d\) 本の disjoint なパスを書く方法のうち、根があるパスの端点になる場合の数
• \([x^d]x_{i,2} \! \in \! \mathbb{N}\): \(1 \! + \! d\) 本の disjoint なパスを書く方法のうち、根があるパスの内部節点になる場合の数

で定めると、答えは（根を \(0\) として）\(\left[x ^ K\right] \! f _ { 0, 0 } +\! \left[x ^ { K - 1 }\right] \! f _ { 0, 1 } + \! \left[x ^ { K - 1 }\right] \!f _ { 0, 2 }\) です。

さらに \(f _ i = f _ { i, 0 } + f _ { i, 1 } y + f _ { i, 2 } y ^ 2\)（\(2\) 変数多項式）とおくと

\[ f _ i = \prod _ { j \lessdot i } \Big \lbrace ( f _ { j, 0 } + f _ { j, 1 } x + f _ { j, 2 } x ) + ( f _ { j, 0 } + f _ { j, 1 } ) y \Big\rbrace \pmod { y ^ 3 } \]

（ただし \(j \lessdot i\) は \(j\) が \(i\) の子であるという意味の独自の記号です）と計算できて、全体で \(O(NK)\) 時間となります。

提出（Rust 2ms)：https://atcoder.jp/contests/tdpc/submissions/53805806