ARC044 B - 最短路問題 - ツバサの備忘録

解法

頂点1が距離0でない場合や、頂点1以外が距離0である場合は、明らかに答えが0になるので処理しておきます。
それ以外のグラフについて考えます。
あらかじめ、距離が $x$ の頂点の個数 $c_{x}$ をそれぞれカウントしておきます。
距離が $x$ である頂点は、距離が $x-1$ である頂点、 $x$ である頂点、 $x+1$ である頂点に向けて辺を張ることができます。 $x+1$ である頂点との辺は、距離が $x+1$ である頂点から張る辺について考慮するときに計算すればよいので、距離が $x$ である頂点について考えるとき、 $x-1$ の頂点と $x$ の頂点に向けて張る辺についてのみ計算していきます。

距離 $x-1$ の頂点に向けての辺の張り方
距離 $x$ の頂点を1つ選びます。すると、この頂点は、距離が $x-1$ である頂点のうちすくなくとも1つの頂点に向けて辺が張られていなければなりません。
今選んだ頂点と、 $c_{x-1}$ 個の頂点との辺の張り方は、 $2^{c_{x-1}}$ 通りありますが、この中で選んではいけないパターンは、どこにも辺が張られていないパターンただ1つです。
ということで、距離 $x$ の頂点1つに対し、距離 $x-1$ の頂点との辺の張り方は $2^{c_{x-1}} - 1$ 通りとなります。
これが、 $c_{x}$ 個の頂点について同じことが考えられるので、最終的に距離 $x$ の頂点と $x-1$ の頂点についての辺の張り方は、
$(2^{c_{x-1}}-1)^{c_{x}}$ 通り
です。
距離 $x$ の頂点同士を結ぶ辺の張り方
距離 $x$ の頂点同士を結ぶ辺の張り方は、 $_{c_{x}}C_{2}$ 通りです。今回は、全ての辺について、張る、張らないの2パターンを自由に選べます。
ということで、
$2^{_{c_{x}}C_{2}}$
通りの張り方が存在します。

ということで、 $a_{i}$ の最大値を $m$ として、
$\displaystyle \prod_{x = 1}^{m} (2^{c_{x-1}}-1)^{c_{x}} \times 2^{_{c_{x}}C_{2}}$
が答えとなります。