解説

UnionFindUndoを持っていますか？僕は持っています。

道路と歩行者でそれぞれ頂点を用意し、それぞれ道路のみ歩行者のみいけるところをつなげておきましょう。

ここで、頂点1の場合で考えてみましょう。

1において、道路のみをつかっていける集合を $V$ とします

$V$ に属する全ての要素を歩行者側にいくことができるので、辺をはります。

そうすると、 $2|V| + (歩行者をつかって追加でいける)$ 頂点数になるので、全体でいける数がわかります。

これが $V$ について全部いえるので $V$ についてはまとめて計算しちゃいましょう。

Undo可能なUnionFindを用いて計算量は $O( (n+ D + E) \log n)$ です

自分自身も含まれることに注意してね

提出コード