F - Maximum Spanning Tree Query
問題文
$N$ 頂点 $M$ 辺からなる、重み付き無向グラフ $G = (V, E)$ が与えられます。 グラフは連結ですが、単純とは限りません。
$i (1 \le i \le M)$ 番目の辺は $u_i, v_i$ を双方向に結んでおり、重みは $c_i$ です。
$Q$ 個のクエリが与えられます。
$j (1 \le j \le Q)$ 番目のクエリでは、重み $w_j$ の辺 $e_j = \{ x_j, y_j \}$ が与えられます。
各クエリについて、次の問題を解いてください。
- グラフ $(V, E \cup e_j)$ の最大全域木 (辺の重みの和が最大となる全域木) の辺の重みの総和を求めよ。
- すなわち、グラフ $G$ に $e_j$ を追加したときの最大全域木の辺の重みの総和を求めよ。
ただし、クエリの前後でグラフ $G$ は変化しないものとします。
制約
- $2 \le N \le 2 \times 10^5$
- $N - 1 \le M \le 2 \times 10^5$
- $1 \le Q \le 2 \times 10^5$
- $G$ は連結
- $1 \le c_i, w_j \le 10^9$
- $1 \le u_i, v_i, x_j, y_j \le N$
- $u_i \ne v_i, x_j \ne y_j$
- 入力はすべて整数である
部分点
この問題はいくつかの小課題に分けられ、その小課題の全てのテストケースに正解した場合に、「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。
- (10 点) $N \le 100, M \le 100, Q \le 1000$
- (15 点) $N \le 100, Q \le 1000$
- (75 点) 追加の制約はない
入力
入力は以下の形式で標準入力から与えられる。
$u_1$ $v_1$ $c_1$
$u_2$ $v_2$ $c_2$
...
$u_M$ $v_M$ $c_M$
$Q$
$x_1$ $y_1$ $w_1$
$x_2$ $y_2$ $w_2$
...
$x_Q$ $y_Q$ $w_Q$
出力
$Q$ 行出力せよ。
$j (1 \le j \le Q)$ 行目には、$j$ 番目のクエリに対する答えを出力せよ。
4 5
1 2 6
1 3 3
1 4 1
2 3 5
2 4 4
2
3 4 10
1 2 10
21
19
初期状態では、以下の図のようになっています。
1 番目のクエリでは、 $3, 4$ 間に重み $10$ の辺 (下図緑の辺) を追加します。
これにより得られる最大全域木は以下の赤い辺で構成されます。
辺の重みの総和は $6 + 5 + 10 = 21$ です。
2 番目のクエリでは、 $1, 2$ 間に重み $10$ の辺を追加します。
グラフは単純とは限らないことに注意してください。
また、クエリの前後でグラフは変化しないことに注意してください。
この入力は、小課題 1, 2, 3 の制約を満たします。
2 1
1 2 3
5
1 2 1
1 2 2
1 2 3
1 2 4
1 2 5
3
3
3
4
5
この入力は、小課題 1, 2, 3 の制約を満たします。
7 10
1 6 15
6 2 62
7 4 83
2 1 98
6 3 74
5 4 45
2 7 8
1 5 36
5 7 54
2 5 40
5
3 2 83
1 7 50
2 4 35
4 5 45
3 5 54
432
421
411
411
425
この入力は、小課題 1, 2, 3 の制約を満たします。