ABC 401-500/ABC420E - Reachability Query - 競技プログラミング用 知識集積所

---

問題

ABC420E

必要知識

B以下レベルの内容は省略

• UnionFind木※

考え方

タイプ1とタイプ3のクエリを見ると、いかにもUnionFind木※の出番。
ただし、タイプ3で同じ連結成分内に黒頂点があるかを全探索※していては間に合わない。

UnionFind木※の中身の構造を参考に、各連結成分の親のところに「その連結成分に何個黒があるか」を保管しておくことを考える。
そうすれば、

• クエリ1のときに、黒頂点数を足して保管しなおす
• クエリ2のときに、黒頂点数も変更する
• クエリ3の時には、黒頂点数が正かどうかを見る

で高速に処理することができる。

これは、自前でUnionFind木※を実装して中身を加工するのが正統な方法であろうが、外付けのvectorで黒頂点数だけ管理しても対応できる。

解答例

解答例

注意点

別解