ABC180 F - Unbranched
蛇足をしてめっちゃ遠回りした・・・
問題
解法
まあ雰囲気がDPなのでDP
最大サイズがLぴったりになる個数を考えたいところだが，連結成分が複数あるときにめちゃめちゃ面倒なことになる(例えば連結成分のサイズの集合を考えた時に{L}とか{L,L,L,L,...}とか{L,L-1,L-2,...}とか色んなのが考えられる）
そこで連結成分の最大サイズがL→
（任意の連結成分の大きさがL以下であるようなグラフ）-（L-1以下であるようなそれ）
と置き換えて，
dp[v][e][t]:頂点をv，辺をeまで使ったときの連結成分の最大サイズがL-t以下になるようなパターン数
を考えればよくて，答えは
dp[n][m][0]-dp[n][m][1]
になる
あとは遷移を考えるのだが，
e==0であればL-tが正の値である限り1通りに決まるのでそれ基準で考える
すると大きく分けて，頂点を1つ付加した（これをxとする）時に以下の遷移が考えられる．
1.xが孤立している
2.xがk-path上にいる(2<=k<=L-t)
3.xがk-cycle上にいる(2<=k<=L-t)
1.の場合，これは単純にもともとできていたグラフに頂点が追加されるだけなのでdp[v-1][e][t]を加算してやればいい．
2.の場合，既に使われているv-k頂点と自分を取り除いたn-(v-k)-1頂点から自分に接続されるk-1頂点を選んでやればいい．あとはk-pathがどの順番で接続されるのかを考えると逆順も考慮してk!/2通りあるので
dp[v][e][t]+=dp[v-k][e-(k-1)][t]*C(n-v-1,k-1)*k!/2
としてやればいい．（k-pathを形成する時に使われる辺の本数はk-1本）
3.の場合，基本的には2と同じなのだが，円順列なのでk頂点でサイクルを構成するときの場合の数はきほんてきには(k-1)!/2通りある．（逆順も考慮）
ただ，k==2の場合，逆順がそもそも自分自身と一致するのでこれだけ場合分けして1通りだけとカウントする．
以上を踏まえると
(k==2)dp[v-k][e-k][t]*C(n-(v-k)-1,k-1)
(k>2)dp[v-k][e-k][t]*C(n-(v-k)-1,k-1)*(k-1)!/2
を加算してやればいいことがわかる．
余談
一回v==eならサイクルの1通りに決まると思ったのだが，よくよく考えると後ろの方の頂点とサイクルを形成する可能性があり（例えば頂点{1,2,3}があったときに1-3でサイクルができるパターン），うまく行かない（これを書いてしまってて，時間を大量に消費した）
