题解：

对整个修改的区间进行分治。对于当前修改区间来说，我们对整幅图中将要修改的边权都先改成-inf，跑一遍最小生成树，然后对于一条树边并且他的权值不为-inf，那么这条边一定就是树边了。然后我们把这些点都缩成一个点。然后，我们继续对当前修改区间来说，我们把要修改的边的边权都修改成inf，跑一遍最小生成树，然后对于一条非树边来说，他的边权不为inf，那么这条边一点是非树边了，然后我们每层缩点，减边，这样图就会越来越小，然后当l == r的时候，我们还原修改操作，最后把跑最小生成树计算答案。

一道神奇的cdq题目。

代码：

1 #include
      
         2 using namespace std;  3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);  4 #define LL long long  5 #define ULL unsigned LL  6 #define fi first  7 #define se second  8 #define pb push_back  9 #define lson l,m,rt<<1 10 #define rson m+1,r,rt<<1|1 11 #define lch(x) tr[x].son[0] 12 #define rch(x) tr[x].son[1] 13 #define max3(a,b,c) max(a,max(b,c)) 14 #define min3(a,b,c) min(a,min(b,c)) 15 typedef pair
       
         pll; 16 const int inf = 0x3f3f3f3f; 17 const LL INF = 0x3f3f3f3f3f3f3f3f; 18 const LL mod =  (int)1e9+7; 19 const int N = 1e5 + 100; 20 struct Node{ 21     int u, v, c, id; 22     bool operator < (const Node & x) const{ 23         return c < x.c; 24     } 25 }e[20][N], f[N], g[N]; 26 int a[N], b[N], ct[N], mapid[N]; 27 int pre[N]; 28 int to[N]; 29 void link(int u, int v){ 30     mapid[to[v]] = 0; 31     mapid[u] = v; 32     to[v] = u; 33 } 34 int Find(int x){ 35     if(x == pre[x]) return x; 36     return pre[x] = Find(pre[x]); 37 } 38 LL ans[N]; 39 void Clear(int tot){ 40     for(int i = 1; i <= tot; i++){ 41         pre[f[i].u] = f[i].u; 42         pre[f[i].v] = f[i].v; 43     } 44 } 45 void contraction(int &tot, LL &sum){ 46     Clear(tot); 47     sort(f+1, f+1+tot); 48     int u, v, zz = 0; 49     for(int i = 1; i <= tot; i++){ 50         u = Find(f[i].u), v = Find(f[i].v); 51         if(u != v){ 52             pre[u] = v; 53             if(f[i].c != -inf){ 54                 sum += f[i].c; 55                 g[++zz] = f[i]; 56             } 57         } 58     } 59     Clear(tot); 60     for(int i = 1; i <= zz; i++){ 61         u = Find(g[i].u); v = Find(g[i].v); 62         pre[u] = v; 63     } 64     zz = 0; 65     for(int i = 1; i <= tot; i++){ 66         u = Find(f[i].u), v = Find(f[i].v); 67         if(u != v){ 68             f[++zz] = f[i]; 69             f[zz].u = u; 70             f[zz].v = v; 71             mapid[f[i].id] = zz; 72         } 73     } 74     tot = zz; 75     return ; 76 } 77 void reduction(int &tot){ 78     Clear(tot); 79     sort(f+1, f+1+tot); 80     int u, v, zz = 0; 81     for(int i = 1; i <= tot; i++){ 82         u = Find(f[i].u); v = Find(f[i].v); 83         if(u != v){ 84             pre[u] = v; 85             f[++zz] = f[i]; 86         } 87         else if(f[i].c == inf) 88             f[++zz] = f[i]; 89     } 90     tot = zz; 91     return ; 92 } 93 void cdq(int l, int r, int now, int tot, LL sum){ 94     if(l == r) ct[a[l]] = b[l]; 95     for(int i = 1; i <= tot; i++){ 96         e[now][i].c = ct[e[now][i].id]; 97         mapid[e[now][i].id] = i; 98         //link(e[now][i]) 99         f[i] = e[now][i];100     }101     if(l == r){102         ans[l] = sum;103         Clear(tot);104         sort(f+1, f+1+tot);105         int u, v;106         for(int i = 1; i <= tot; i++){107             u = Find(f[i].u), v = Find(f[i].v);108             if(u != v){109                 pre[u] = v;110                 ans[l] += f[i].c;111             }112         }113         return ;114     }115     for(int i = l; i <= r; i++) f[mapid[a[i]]].c = -inf;116     contraction(tot, sum);117     for(int i = l; i <= r; i++) f[mapid[a[i]]].c = inf;118     reduction(tot);119     for(int i = 1; i <= tot; i++) e[now+1][i] = f[i];120     int mid = l+r >> 1;121     cdq(l, mid, now+1, tot, sum);122     cdq(mid+1, r, now+1, tot, sum);123 124 }125 int main(){126     int n, m, q;127     scanf("%d%d%d", &n, &m, &q);128     for(int i = 1; i <= m; i++){129         scanf("%d%d%d", &e[0][i].u, &e[0][i].v, &e[0][i].c);130         e[0][i].id = i;131         ct[i] = e[0][i].c;132     }133     for(int i = 1; i <= q; i++)134         scanf("%d%d", &a[i], &b[i]);135     cdq(1,q,0,m,0);136     for(int i = 1; i <= q; ++i)137         printf("%lld\n", ans[i]);138     return 0;139 }