AtCoder Beginner Contest 180 F - Unbranched - アルゴリズム忘備録

各連結成分のサイズの最大値がちょうど $L$ という条件なので、最大値が $L$ 以下の場合の数から最大値が $L-1$ 以下の場合の数を引くことを考える。

$dp_L[n][m]$ を「サイズ $L$ 以下の連結成分の集合で、頂点数が $n$ 個、辺の数が $m$ 本であるときの場合の数」とする。これに $N-n$ 個の残りの頂点から点を追加していく遷移を考える。頂点の次数が2以下であるということは、各連結成分はループまたはパスになっている。そのため、素直に考えると $k$ 個の点を新たに追加するときはパスの場合 $C(N-n, k) * k! / 2$ 、ループの場合 $C(N-n, k) * (k-1)! / 2$ となる（ただし、 $k=2$ の場合は別に考える）。しかし、この方針だと連結成分同士の順列の分の重複を考える必要が出てくるため、dpの状態として連結成分の状態を保つ必要があり、 $O(LMN^2)$ とかになってしまう。

そのため、 $k$ 個の新規に追加する頂点のうち1個は残りの頂点のうち最小のインデックスを持つ頂点にする、という制約を加える（他の頂点はなんでもよい）。すると連結成分同士の順列を考えなくて良くなる。この場合、パスの場合 $C(N-n-1, k-1) * k! / 2$ 、ループの場合 $C(N-n-1, k-1) * (k-1)! / 2$ となる（同様に $k=2$ の場合は別に考える）。これは素直に書くと $O(NML)$ になり間に合う。