$v$ を固定したときの部分問題は $A_i$ と $B_i$ ( ただし $i$ は $1$ から $v$ までの最短路に含まれる頂点 ) を結ぶ辺を追加した $N$ 頂点のグラフについて、連結成分のうち木の個数 $T$ が分かっていれば答えは $N-T$ と求められます。 ( 参考 : ARC )

よって各連結成分ごとに、その代表元に連結成分が木であるかを保存することを考えると公式解説で要求されるようなデータ構造などがあればよく、 Rollback-Union-Find などで実現できます。