この解説は「BFS木」と呼ばれる概念を知っていると理解しやすいです。ABC の過去問 (ネタバレ注意) にも登場している考え方ですので、聞いたことがない方はぜひ調べてみてください。

頂点 \(1\) から頂点 \(u\) までの最短距離を \(d_u\) と表します。
\(d_1\) は必ず \(0\) であり、\(d_2, \dots, d_N\) の値を決め打ったとき、「\(d_u\) が頂点 \(1\) から頂点 \(u\) までの最短距離である」という条件が成り立つことは、辺が次の条件を満たすことと同値です。

• 全ての \(u = 2, \dots, N\) に対し、\(d_v + 1 = d_u\) を満たすような頂点 \(v\) と \(u\) を結ぶ辺が少なくとも一つ存在する。
• \(|d_u - d_v| \geq 2\) であるような頂点 \(u, v\) を結ぶ辺は存在しない。

\(d_1, \dots, d_{N-1}\) がいずれも \(d_N\) より小さいような \((d_1, \dots, d_N)\) の組全てに対して、上の条件を満たすような辺の集合の総数を数え上げればよいです。
上の条件を満たす \((d_1, \dots, d_N)\) と辺の集合の組は、以下の操作によって重複なく構成することができます。

• \(d_1 = 0, d_2 = \dots = d_N = \infty\) と初期化する。また、整数 \(n\) を \(n = 0\) で初期化する。
• 次の操作を \(u \neq N\) かつ \(d_u = \infty\) となる \(u\) が存在する間繰り返す。
  • \(u \neq N\) かつ \(d_u = \infty\) を満たす \(u\) を \(\bold{1}\) 個以上好きな個数選び、\(u_1, \dots, u_k\) とおく。
  • 各 \(u_i\) に対し、\(d_v = n\) となる \(v\) を \(\bold{1}\) 個以上好きな個数選び、それぞれに対して辺 \((v, u_i)\) を追加する。また、\(d_{u_i}\) の値を \(n+1\) で置き換える。
  • \(1 \leq i \lt j \leq k\) を満たす \((i, j)\) を \(\bold{0}\) 個以上好きな個数 選び、それぞれに対して辺 \((u_i, u_j)\) を追加する。
  • \(n\) の値を \(1\) 増やす。
• 各 \(u_i\) に対し、\(d_v = n\) となる \(v\) を \(\bold{1}\) 個以上好きな個数選び、それぞれに対して辺 \((v, N)\) を追加する。また、\(d_{N}\) の値を \(n+1\) で置き換える。

この操作の手順を次の動的計画法に落とし込むことで数え上げることができます。

• \(\mathrm{dp}_{n, k} :=\)「\(d_u \neq \infty\) であるような \(u\) が \(n\) 個あり、そのうち \(d_u\) が最大であるものが \(k\) 個あるようにする方法の総数」

状態数が \(O(N^2)\)、それぞれに対して遷移が \(O(N)\) となり、この問題を \(O(N^3)\) で解くことができました。