undoつきUnion-Find
Codeforces
CodeforcesR2600
CodeforcesDIV1-D
データ構造
クエリ処理問題
クエリ(グラフ上)
クエリ(木上)
Union-Find
undoつきUnion-Find
Union-Findのマージ過程を表す木を考える
永続Union-Find
クエリ:削除
Eulerツアー
セグメント木
色に関する問題
グラフ問題
クエリ先読み
後ろから解く
操作を逆順に見る
個人的要復習
いろんな方法がありそう。Union-Find のマージ過程を表す木でやったけど、ほかにも Undo 付き Union-Find を使うなど 問題へのリンク 問題概要 頂点数 、辺数 のグラフが与えられる。初期状態では各頂点に という値がついている (すべて 1 以上で disjoint)…
Codeforces
グラフ問題
クエリ処理問題
O(N^2)個のものを考える問題
二部グラフ
二部グラフ判定
Union-Find
グラフの頂点を倍加する
DP状態:あまり
クエリ:削除
色に関する問題
ならし計算量解析
undoつきUnion-Find
CodeforcesDIV1-C
CodeforcesR2500
undo 付き Union-Find ってなんぞ！？ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。色が 種類あって、各頂点は のいずれかの色で塗られている。このとき、以下の条件を満たすような色の組 () の個数を求めよ。 個の頂点のうち、色…
