AtCoder Beginner Contest 264 E問題 Blackout 2

$N$ 個の都市と $M$ 個の発電所からなる国がある. これらを総称して地点と呼ぶ.

$N$ 個の都市は地点 $1, \dots, N$ と, $M$ 個の発電所は地点 $(N+1), \dots, (N+M)$ と名付けられている.

この国には $E$ 本の電線があり, $j$ 番目の電線は地点 $U_j$ , 地点 $V_j$ を結ぶ.

ここから $Q$ 個のイベントがおこる. 各イベントが起こった後の状況に対して, 以下の問に答えよ.

問題は次のようにしてグラフの問題に帰着できる.

無向グラフ $G=(V,F)$ が与えられる. ただし,

次の操作をし, 操作を施した後のグラフについて, 以下の問に答えよ.

ここで, 一般的に連結性については "辺を削除する" 操作より "辺を追加する" 操作に対する処理の方が速い事が多い. 今回もその性質を使う. つまり, 次のような問題に変換する.

無向グラフ $G=(V,F)$ が与えられる. ただし,

$q=Q,Q-1, \dots, 1$ の順に以下の問に答えた後, 操作を施せ.

このとき, 辺の追加と連結性の判定を得意とするデータ構造は Union Find である. この Union Find を利用する. このとき, 各連結成分に対して, 次のような状態及び, 状態をマージする関数を用意する.

状態: $S:=\mathbb{N} \times \mathbb{N}$
マージ関数: $\mu: S \times S \to S; \quad ( (a_t, a_p), (b_t, b_p) ) \mapsto (a_t,+b_t, a_p+b_p)$

ここで, $a=(a_t, a_p) \in S$ はその連結成分に都市が $a_t$ 個, 発電所が $a_p$ 個ある事に対応する.

これを利用して, 次のようにして正解できる. ただし, $q$ 番目の操作後における解答を $A_q$ と表すことにする.

$K$ を $(N+M)$ 頂点からなる Union Find とする.
頂点 $1,2, \dots, N$ の状態を $(1,0)$ に, 頂点 $(N+1),\dots, (N+M)$ の状態を $(0,1)$ に設定する.
$j=X_q$ となる $q$ が存在しない全ての $j$ に対して, $K$ に対して頂点 $U_j, V_j$ に辺を加えてマージする.
$K$ の各連結成分 $g$ に対して, $g$ の状態を $a=(a_t,a_p)$ としたとき, $a_p \gt 0$ ならば, $A_Q$ に $a_t$ を加える.
の順に次を行う.
- $A_{q-1} \gets A_q$
- において, 頂点が非連結な場合, 以下を行う.
  - 頂点 $U_{X_q}$ が属する連結成分の状態を $(a_t, a_p)$ , 頂点 $V_{X_q}$ が属する連結成分の状態を $(b_t, b_p)$ とする.
  - $a_p \gt 0$ かつ $b_p=0$ ならば, $A_{q-1}$ に $b_t$ を加算する.
  - $a_p=0$ かつ $b_p \gt 0$ ならば, $A_{q-1}$ に $a_t$ を加算する.
  - $\mu$ をマージ関数として, 頂点 $U_{X_q}, V_{X_q}$ に辺を加えてマージする.