問題を次のように言い換えることができます．

• 各頂点を白か黒に塗る．黒に塗るときは重み \(A_i\) をかける． その後，辺を縮約していく． 縮約する \(2\) 頂点は同じ色でなくてはならない． 元の色が白だった場合，縮約後の頂点の色は白か黒で選べる． 元の色が黒だった場合，縮約後の頂点の色は黒である． 最終的に残る頂点の色が黒であるような操作方法は何通りあるか？

木DPを行います． 頂点 \(v\) を根とするサイズ \(n\) 部分木 \(t\) の情報として，\(t\) 内の辺だけで縮約を行った場合の様子を考えて，以下のように \(A,B_1,\cdots,B_{n-1},C_0,\cdots,C_{n-1}\) を管理します．

• \(A\) : \(v\) の初期状態が黒であった場合に対応する操作方法の数． \(v\) が黒であることから，この \(t\) だけを考えても操作が完結する．
• \(B_i\) : \(v\) の初期状態が白で，かつ \(i\) 回目の操作で \(v\) (が元となっている頂点) が黒に変わるような操作方法の数． この場合でも，\(t\) だけで操作が完結する．
• \(C_i\) : \(v\) の初期状態が白で，かつ \(i\) 回目の操作の直後に \(t\) 外部の頂点との縮約によって \(v\) が黒に変わるような操作方法の数． この場合は \(t\) だけでは操作は完結していない．

\(t\) の内外にまたがるような縮約操作は何度も起こる可能性がありますが，そのうち重要なのが頂点の色が変わる操作だけであることに注目すると，\(t\) 内の操作の様子を以上の \(3\) パターンにまとめることができます．

あとはこれらの値を定義に沿って計算してみると，DP可能な形になっています． 累積和等を用いて計算すれば，サイズ \(n\) と \(m\) の部分木のマージが \(O(nm)\) で行えるため，計算量は全体で \(O(N^2)\) になります．

実装例