パスを書くだけでなく、次のように頂点を白と黒に塗り分ける場合の数を数えます。

• どのパスにも属さない頂点は白く塗る
• パスの LCA である頂点は白く塗る
• それ以外の頂点は黒く塗る

このとき、根は必ず白頂点になることに注意です。

木 DP で解きましょう

部分木の状態を、部分木の根の色で分類して数えましょう。部分木内外にまたがる予定のパスは「未解決のパス」と呼んでおき、パスの本数には数えないことにします。

• \([x^d] f _ i(x)\): 根 \(i\) が白頂点で、解決済みのパスが \(d\) 本
• \([x^d] g _ i(x)\): 根 \(i\) が黒頂点で、解決済みのパスが \(d\) 本

このとき、次の木 DP で計算できます。

\[ \begin{aligned} h _ i (x, y) &= \prod _ { j \lessdot i } \left( f _ j ( x ) + g _ j ( x ) y \right) \\ f _ i (x) &= \left( [1] + [y]x + [y^2]x \right) h _ i ( x, y) \\ g _ i (x) &= \left( [1] + [y] \right) h _ i ( x, y) \end{aligned} \]

ただし

• \(j \lessdot i\) は \(j\) が \(i\) の子であるという意味の独自の記号です。
• 係数取得演算子 \([1], [y], [y^2]\) は、\(x\) の係数は絞らずに \(y\) の係数だけを絞ることにします。

答えは \([x^K]f_0(x)\) (ただし \(0\) が根) です。

Rust 9 ms