Problem

动态改边后询问 MST。

Solution

对操作分治。
设待修改边为 INF，去掉不可能作为 MST 的边。
设待修改边为 -INF，缩点一定作为 MST 的边。
递归分治将问题规模减半。

似乎没有严格复杂度证明。

// Code by ajcxsu
// Problem: city

#include<bits/stdc++.h>
#define INF (0x3f3f3f3f)
using namespace std;

const int N=20010, M=50010;
struct Edge { int id, u, v, w; } ;
struct Query { int x, w; } ;
bool cmp(const Edge &a, const Edge &b) { return a.w<b.w; }

int idx=0;
int Find(int t[], int fa[], int x) {
    if(t[x]!=idx) t[x]=idx, fa[x]=0;
    return fa[x]?fa[x]=Find(t, fa, fa[x]):x;
}
bool Union(int t[], int fa[], int a, int b) {
    int af=Find(t, fa, a), bf=Find(t, fa, b);
    if(af==bf) return false;
    return fa[af]=bf, true;
}

typedef long long ll;
ll tot[M];
int fa[N], fa2[N], fa3[N];
int t1[N], t2[N], t3[N];
int del[M];

void solve(int l, int r, vector<Query> q, vector<Edge> e, ll ans) {
    idx++;
    vector<Edge> e2=e;
    if(l!=r) for(auto x:q) e2[x.x].w=-INF;
    else for(auto x:q) e2[x.x].w=x.w;
    sort(e2.begin(), e2.end(), cmp);
    for(auto x:e2) if(Union(t1, fa, x.u, x.v)) {
        if(x.w!=-INF) Union(t2, fa2, x.u, x.v), ans+=x.w;
    }
    if(l==r) { tot[l]=ans; return; }
    e2=e;
    for(auto x:q) e2[x.x].w=INF;
    sort(e2.begin(), e2.end(), cmp);
    for(auto x:e2) if(!Union(t3, fa3, x.u, x.v) && x.w!=INF) del[x.id]=idx;
    e2.clear();
    for(auto x:e) {
        x.u=Find(t2, fa2, x.u), x.v=Find(t2, fa2, x.v);
        if(x.u!=x.v && del[x.id]!=idx) e2.push_back(x);
    }
    e2.resize(e2.size());
    unordered_map<int, int> mp;
    for(int i=0, j=e2.size(); i<j; i++) 
        mp[e2[i].id]=i, e2[i].id=i;
    for(auto &x:q) x.x=mp[x.x];
    vector<Query> lq, rq;
    int mid=(l+r)>>1;
    for(int i=l; i<=mid; i++) lq.push_back(q[i-l]);
    for(int i=mid+1; i<=r; i++) rq.push_back(q[i-l]);
    solve(l, mid, lq, e2, ans);
    for(auto x:lq) e2[x.x].w=x.w;
    solve(mid+1, r, rq, e2, ans);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m, q;
    cin>>n>>m>>q;
    vector<Edge> e;
    vector<Query> qu;
    int u, v, w;
    for(int i=0;i<m;i++) cin>>u>>v>>w, e.push_back({i, u, v, w});
    for(int i=1;i<=q;i++) cin>>u>>w, qu.push_back({u-1, w});
    solve(1, q, qu, e, 0);
    for(int i=1;i<=q;i++) cout<<tot[i]<<endl;
    return 0;
}