問題
$N$ 頂点のグラフに対して $Q$ 個の更新クエリが与えられる。各クエリは以下のいずれか：
add u v w: 辺 $(u, v, w)$ を追加するremove id: 辺 $id$ を削除する（$id$ は追加された順番の 1-indexed）query: 現在のグラフの最小全域木の重みを出力する（連結でない場合は-1）
制約
$2 \le N \le 300$
$1 \le Q \le 3000$
$1 \le w \le 10^9$
追加する辺の総数 $\le 3000$
時間制限: 4秒
入出力例
入力例 1
4 8
add 1 2 3
add 2 3 5
add 3 4 2
query
remove 2
add 1 4 4
query
remove 1出力例 1
10
9クエリ1: 辺{1-2:3, 2-3:5, 3-4:2}でMST=3+5+2=10。クエリ2: 辺{1-2:3, 3-4:2, 1-4:4}でMST=3+2+4=9
概念図: 辺の存在区間と時刻軸管理
ヒント（段階的開示）
ヒント1: 方向性
辺の存在期間を時刻軸区間として管理します。各
add で辺の開始時刻を記録し、remove で区間を確定させます。各 query 時刻で有効な辺集合に Kruskal 法を適用します。
ヒント2: アプローチ
- 各辺の存在区間 $[s, e]$ を記録（削除なし辺は $[s, Q-1]$）
- 各
query時刻 $t$ に対し、$s \le t \le e$ を満たす辺の集合を取得 - Kruskal 法で MST を計算（連結でなければ $-1$）
- $N \le 300$ なので Kruskal は $O(M \log M)$ で高速
ヒント3: 辺区間管理の実装骨格
add_time = {} # edge_id -> (time, u, v, w)
edge_intervals = [] # (u, v, w, start, end)
edge_count = 0
for t, op in enumerate(ops):
if op[0] == 'add':
edge_count += 1
add_time[edge_count] = (t, op[1], op[2], op[3])
elif op[0] == 'remove':
eid = op[1]
s, u, v, w = add_time.pop(eid)
edge_intervals.append((u, v, w, s, t - 1))
# 残存辺を最後にループ後処理
for eid, (s, u, v, w) in add_time.items():
edge_intervals.append((u, v, w, s, Q - 1))模範解答 (Python)
import sys
from sys import stdin
def solve():
data = stdin.read().split()
idx = 0
N, Q = int(data[idx]), int(data[idx+1]); idx += 2
ops = []
for _ in range(Q):
op = data[idx]; idx += 1
if op == 'add':
u, v, w = int(data[idx]), int(data[idx+1]), int(data[idx+2])
idx += 3
ops.append(('add', u, v, w))
elif op == 'remove':
eid = int(data[idx]); idx += 1
ops.append(('remove', eid))
else:
ops.append(('query',))
edges = []
add_time = {}
edge_count = 0
query_times = []
for t, op in enumerate(ops):
if op[0] == 'add':
edge_count += 1
add_time[edge_count] = (t, op[1], op[2], op[3])
elif op[0] == 'remove':
eid = op[1]
s, u, v, w = add_time.pop(eid)
edges.append((u, v, w, s, t - 1))
else:
query_times.append(t)
for eid, (s, u, v, w) in add_time.items():
edges.append((u, v, w, s, Q - 1))
def kruskal(n, edge_list):
parent = list(range(n + 1))
rank = [0] * (n + 1)
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px
if rank[px] == rank[py]:
rank[px] += 1
return True
edge_list_sorted = sorted(edge_list, key=lambda e: e[2])
total = 0
cnt = 0
for u, v, w, *_ in edge_list_sorted:
if union(u, v):
total += w
cnt += 1
return total if cnt == n - 1 else -1
results = []
for qt in query_times:
active = [(u, v, w, s, e) for (u, v, w, s, e) in edges if s <= qt <= e]
results.append(kruskal(N, active))
print('\n'.join(map(str, results)))
solve()
Step-by-Step 解説
1辺の存在区間管理
各辺が
各辺が
add されてから remove されるまでの時刻区間 $[s, e]$ を記録します。削除されなかった辺は $[s, Q-1]$。
2クエリ時刻の特定
query 操作が発生する時刻 $t$ を列挙し、その時刻 $t$ に有効な辺（$s \le t \le e$）を集めます。
3Kruskal 法の適用
有効辺の集合を重みでソートし、Union-Find で MST を構築。辺数が $N-1$ に達しない場合は連結でないので $-1$。
有効辺の集合を重みでソートし、Union-Find で MST を構築。辺数が $N-1$ に達しない場合は連結でないので $-1$。
4計算量の分析
辺の総数 $M \le 3000$、クエリ数 $K \le Q$。各クエリで $O(M \log M)$ の Kruskal を実行するので全体 $O(QM \log M)$。
辺の総数 $M \le 3000$、クエリ数 $K \le Q$。各クエリで $O(M \log M)$ の Kruskal を実行するので全体 $O(QM \log M)$。
5大規模入力への対応
$N, Q$ が大きい場合は Offline Dynamic MST（時刻軸セグメント木 + Undo DSU + 重みのランキング）を使います（Day035 Q5）。
$N, Q$ が大きい場合は Offline Dynamic MST（時刻軸セグメント木 + Undo DSU + 重みのランキング）を使います（Day035 Q5）。
計算量
辺の区間管理: $O(Q)$
各クエリの Kruskal: $O(M \log M + M \alpha(N))$
全体: $O(Q \cdot M \log M)$
空間: $O(M + N)$
各クエリの Kruskal: $O(M \log M + M \alpha(N))$
全体: $O(Q \cdot M \log M)$
空間: $O(M + N)$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| remove 後の辺の端点を正しく閉じない | end を t-1 でなく t にする | edges.append((u,v,w,s,t-1)) |
| 削除されなかった辺を無視 | add_time が空にならない | ループ後に残存 add_time を処理 |
| union-find の再利用 | kruskal 内で parent を再初期化しない | parent = list(range(n+1)) を毎回作成 |
| query の時刻を ops インデックスと混同 | query_times に何を入れるか | ops のインデックス（時刻）を記録 |
次のステップ
- 発展問題: $N, Q \le 10^5$ での Offline Dynamic MST（時刻軸セグメント木 + Undo DSU）
- 関連: Day022 Q3（動的最小全域木）、Day035 Q5（Offline Dynamic MSF）
- 応用: 辺重みを動的に変更しながら MST を維持するクエリ