undoつきUnion-Find
AtCoder
ABC-Ex
橙色diff
Union-Find
木
差分更新
undoつきUnion-Find
データ構造
クエリ処理問題
操作:削除
N個のペア値の問題
種類数
高度典型
木の問題に対してパスの場合から考える
DFS
グラフテク:値A[i]を頂点に持たせる
各kに対して
解空間:O(2^N)通りの選択肢
最大スコア
AtCoder625点
最適化問題
undo 付き Union-Find! 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には、数値 の書かれたボールと、数値 の書かれたボールがある。 各 に対して、次の問に答えよ。 パス - 上の各頂点から ボールを 1 個ずつ選んだときの ボールに書かれた数…
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 ってなんぞ!? 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。色が 種類あって、各頂点は のいずれかの色で塗られている。このとき、以下の条件を満たすような色の組 () の個数を求めよ。 個の頂点のうち、色…