考察
辺重みが1..10と極端に小さい。G_k を重み k 以下の辺だけの graph とすると、Kruskal の telescoping から MST 重みは Σ_{k=0}^{9}(components(G_k)−1) で表せる。辺 (u,v,w) の追加は全 k≥w の G_k に同じ connectivity edge を追加するだけで、削除がないため各 threshold を Union-Find で独立管理できる。MST の重み w は「重み≥1,…,w の層を一つずつ払う」と分解でき、層 k+1 で必要な辺数が c(G_k)−1 になる。k≥w の各 DSU で u,v が別 component の時だけ answer を1減らすと、Σ(c_k−1) を直接維持できる。
採用する候補: 重み threshold 0..9 ごとの DSU と component 数を持ち、追加辺を該当 threshold 全てへ unite する。
threshold 数が定数10で、union 成功のたび components が1減りMST和も1減るため一 query ほぼ定数で更新できる。
棄却する候補: 各辺追加後に全辺を重み順に走査して Kruskal 法をやり直す。
辺数が Q とともに増え、全 query 合計が O(Q(N+Q)) になる。
10個の DSU を初期化し、初期木の各辺 (a,b,c) を k=c..9 へ unite する。component 数から ans=Σ_{k=0}^9(c_k−1) を作る。query (u,v,w) では k=w..9 で unite が成功するたび ans-- し、更新後 ans を出力する。
典型の発動条件
小重みの threshold 分解
発動条件: 重み種類数 W が小さく、MST/最小 bottleneck 情報を追加辺下で維持するとき。
重み≤k の連結性を全 k で持ち、目的値を component 数の層和にする。
追加専用 connectivity の並列 DSU
発動条件: 複数の単調な edge filter graph に同じ追加が波及するとき。
filter ごとに Union-Find を持ち、successful union だけ集約量へ反映する。
問題固有の要素
動的 MST の一般データ構造ではなく、重み上限10を使って MST重みそのものを connectivity layers の面積として表す。
別の問題へ持ち帰る視点: 重み値域が小さいとき、weighted quantity を threshold indicator の総和へ主客転倒する。
正当性
重みk以下graphの成分数c_kについてMST和はΣ_{k=0}^{W−1}(c_k−1)。追加辺重みwはk≥wだけを変え、union成功ごとc_kが1減る。従って各成功で答え1減算が正確で再MST不要。
実装上の注意
- G_0 は辺なし、G_10 は常に連結で和には k=0..9 を使う。追加重み w の辺は threshold k≥w だけへ入れる。
復習の核
- MST辺一本の重みを threshold 層へ分解し、Σ(c_k−1) の式を自分で telescoping する。DSU merge失敗時に答えを変えない。
計算量と制約
時間
N頂点Q追加、重み上限W=10。10 DSUで O(W(N+Q)α(N))。
空間
W個DSUで O(WN)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 1 \leq Q \leq 2 \times 10^5; 1 \leq a_i < b_i \leq N; 1 \leq u_i < v_i \leq N; 1 \leq c_i, w_i \leq 10; The graph is connected before processing the queries.; All input values are integers.
出典