Description
(n) 个点 (m) 条边的带边权无向图。(q) 次操作，每次修改一条边的权值。
求每次修改后的最小生成树的边权和。
Hint
(1le nle 2 imes 10^4, 1le m, qle 5 imes 10^4, 1le ext{边权}le 5 imes 10^7)
Solution
考虑对时间进行分治，( extbf{solve}(l, r)) 表示处理第 (l) 到第 (r) 个操作，并对原图生效这些修改的过程。
显然如果在 (l = r) 时直接将 (m) 条边放一起跑 MST 那好像是为了分治而分治。分治是将问题划分达到 减小规模 的目的，然而这里在 ( extbf{solve}) 的每一层中我们的问题规模并没有变。
求 MST 的时间消耗主要取决于在 边的规模。思考如何可以把边的规模缩小。
首先我们将当前 ( extbf{solve}(l, r)) 过程的边进行分类：动态边（存在一个在 ([l, r]) 中的操作对该边进行了修改）以及 静态边（没有位于 ([l, r]) 的对其修改的操作）。
动态边，对于当下来说，是不能随便剪掉的，于是着重对静态边考虑。其中有一部分边是当前及之后的分治中 必定会选中的边，还有是 必定不会选的边。对于必定会选中的边，我们完全可以把这些边跑 Kruskal 先在 ( extbf{solve}(l, r)) 中做掉，这和在分治终点处做 (r-l+1) 遍的效果是一样的；而对于必定不会选的边，在 ( extbf{solve}(l, r)) 中直接扔掉也无妨，因为这些边迟早会在分治终点处再扔 (r-l+1) 遍。
现在要做的就是设计这两个过程，这里分别记为 ( extbf{contraction}) 和 ( extbf{reduction})。
-
( extbf{contraction})
我们先将所有当前的动态边都在并查集中连上，然后再一个个连静态边，并记录下来所有成功连上的静态边。这些成功连上的就是必选边。这里一开始就连动态边，旨在把这些边按修改地尽量小考虑（此处相当于令动态边权 (=-infty)），也就是说不管这些边会被改的多小，那些成功连上的照样选上。
-
( extbf{reduction})
我们先把所有当前的动态边都略过，只连静态边，并记录未成功连上的边。这些未成功连上的就是无用边。这里将动态边直接忽略，旨在把这些边按修改地尽量大考虑（此处相当于令动态边权 (=+infty)），即无论这些动态边被改大到什么地步，给静态边留了多少的余地，这部分为成功连上的对结果仍然没有贡献。
通过这两个过程，边的规模得到了减小。那么具体减到多小呢？
( extbf{contraction}) 中，我们有不超过 (r-l+1) 条动态边，于是就有不少于 (n-(r-l+1)-1) 条必选边。这些边会使原图中的连通块消至 (O(r-l+1)) 的规模；( extbf{reduction}) 中，由于 ( extbf{contraction}) 后需要考虑的点数已经缩小至区间长度级别，那么有用的边只能有点数规模这么多。
于是总复杂度 (T(n) = 2T(frac n 2) + O(nlog n) = O(nlog^2 n))。
最后在分治的终点，记得先修改，然后把当前边集中剩下的一点也给做掉记录答案。
具体实现时其实还有许多细节：
- 并查集需要支持撤销，于是不能用路径压缩，只能启发式、按秩合并。
- 如果
solve函数中有用vector作为参数表示当前边集的话，千万不要加&引用。左边递归后再到右侧会把边集改掉然后出大问题。 - 不开
long long见祖宗。
Code
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : HNOI2010 城市建设
*/
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e4 + 5;
const int M = 5e4 + 5;
int n, m, Q;
struct unionFind{
int fa[N], siz[N];
int stk[N], top;
void reset(int n) {
for (int i = 1; i <= n; i++)
fa[i] = i, siz[i] = 1;
top = 0;
}
int find(int x) {
return x == fa[x] ? x : find(fa[x]);
}
void merge(int x, int y) {
if ((x = find(x)) == (y = find(y))) return;
if (siz[x] > siz[y]) swap(x, y);
fa[x] = y, siz[y] += siz[x], stk[++top] = x;
}
void back(int t) {
while (top > t) {
int x = stk[top--];
siz[fa[x]] -= siz[x], fa[x] = x;
}
}
} ufs;
struct Edge {
int u, v, w;
inline bool operator < (const Edge& rhs) const {
return w < rhs.w;
}
} e[M];
struct Query {
int k, d;
} q[M];
long long ans[M];
bool vis[M];
bool cmp(const int& x, const int& y) {
return e[x] < e[y];
}
void contraction(int l, int r, vector<int>& can_e, long long& val) {
int backtr = ufs.top; vector<int> rec;
sort(can_e.begin(), can_e.end(), cmp);
for (int i = l; i <= r; i++) ufs.merge(e[q[i].k].u, e[q[i].k].v);
for (auto i : can_e) if (!vis[i]) {
int u = ufs.find(e[i].u), v = ufs.find(e[i].v);
if (u != v) rec.emplace_back(i), ufs.merge(u, v), val += e[i].w;
}
ufs.back(backtr);
for (auto i : rec) ufs.merge(e[i].u, e[i].v);
}
void reduction(vector<int>& can_e) {
int backtr = ufs.top; vector<int> rec;
sort(can_e.begin(), can_e.end(), cmp);
for (auto i : can_e)
if (vis[i]) {
rec.emplace_back(i);
} else {
int u = ufs.find(e[i].u), v = ufs.find(e[i].v);
if (u != v) ufs.merge(u, v), rec.emplace_back(i);
}
ufs.back(backtr), rec.swap(can_e);
}
void solve(int l, int r, vector<int> can_e, long long val) {
if (l == r) e[q[l].k].w = q[l].d;
int backtr = ufs.top;
if (l == r) {
sort(can_e.begin(), can_e.end(), cmp);
for (auto i : can_e) {
int u = ufs.find(e[i].u), v = ufs.find(e[i].v);
if (u != v) ufs.merge(u, v), val += e[i].w;
}
ans[l] = val;
return ufs.back(backtr);
}
for (int i = l; i <= r; i++) vis[q[i].k] = 1;
contraction(l, r, can_e, val), reduction(can_e);
for (int i = l; i <= r; i++) vis[q[i].k] = 0;
int mid = (l + r) >> 1;
solve(l, mid, can_e, val), solve(mid + 1, r, can_e, val);
return ufs.back(backtr);
}
signed main() {
ios::sync_with_stdio(false);
cin >> n >> m >> Q, ufs.reset(n); vector<int> tmp;
for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
for (int i = 1; i <= m; i++) tmp.emplace_back(i);
for (int i = 1; i <= Q; i++) cin >> q[i].k >> q[i].d;
solve(1, Q, tmp, 0ll);
for (int i = 1; i <= Q; i++) cout << ans[i] << endl;
return 0;
}