各頂点の距離が決まっている場合を考えます。

張られている辺は以下の条件を満たす必要があり、かつ以下の条件さえ満たせばよいです。

• 距離が \(i\) の頂点は、少なくとも距離 \(i-1\) の頂点 \(1\) 個と結ばれている。
• 距離が等しい頂点間の辺の有無は任意である。
• 距離が \(2\) 以上離れた頂点間に辺は存在しない。

上の議論をもとに動的計画法によりこの問題を解きます。

\(dp[i][j][k][l][s]\) を、今距離が \(i\) 以下であるような頂点のインデックスを決め、距離が \(i\) 以下の頂点同士を結ぶ辺を上の条件を満たすように \(j\) 本貼り、距離が偶数の頂点が \(k\) 個、奇数の頂点が \(l\) 個あり、特に距離が \(i\) である頂点は \(s\) 個あるような場合の数

と定義します。\(i\) が偶数のときの \(i+1\) への遷移を確認します。

まず、追加する頂点の個数を \(x\) と決めます。このとき、インデックスの割り当て方は \(\binom{N-k-l}{x}\) 通りです。

次に、

• 距離が \(i\) の頂点は、少なくとも距離 \(i-1\) の頂点 \(1\) 個と結ばれている。

という条件を考慮します。\(x\) 個の頂点それぞれについて、距離 \(i\) の頂点とつながる個数を全探索することでこの条件を満たすように辺を張ります。最後に、距離 \(i+1\) 同士の頂点間について自由に辺の張り方を決めます。

この辺の張り方は距離 \(i,i+1\)の頂点数にのみ依存するので、

\(f(x,y,z)\) を距離 \(i\)の頂点が \(x\) 個、距離 \(i+1\) の頂点が \(y\) 個あり、距離 \(i\) と \(i+1\) の頂点間及び距離 \(i+1\) 同士間の辺を \(z\) 本貼る場合の数

と定義すると、上述の方法で前計算できます。

ここで、先ほど定義した dp で、具体的な \(i\) の値は遷移に必要ないことに注意します。\(i\) の偶奇のみが重要なので、状態数を \(O(N^5)\) に減らすことが出来ます。

Writer の方針では遷移に \(O(N^3)\) かかり、計算量は \(O(N^8)\) になりますが、定数倍が非常に軽い（様々なところで \(\frac{1}{2}\) 倍などが掛かります）ので十分余裕をもって間に合います。