根付き木にして葉側から木 DP をします。具体的には、 \( 0\le k\le 2,\ 1\le i\le N,\ 0\le x\le K\) の範囲で

\({\rm dp}[k][i][x]\): 頂点 \(i\) を根とする部分木において、うなぎが \(x\) 本あり、かつ頂点 \(i\) の（親方向を除く）隣接辺のうちうなぎの一部になっている辺は \(k\) 本である場合の数

のように定義します。 \(k=0,\ 1\) のときはうなぎは親方向にもつながっているかもしれません。この DP は、各頂点において（その子たちの情報を既知とすると）ナップサック問題を解く要領で更新できます。 子の数が \(C\) 個の頂点は \(O(CK^2)\) で更新できるので、 全体の計算量は \(O(NK^2)\) です。