Luogu

分析

对修改时间分治，假设当前的时间区间是 $[L,R]$。

考虑以下两种操作：

• 把 $[L,R]$ 中要修改的所有边修改成 $-\infty$，然后求一遍最小生成树。

  发现，如果一条非 $-\infty$ 边在最小生成树中，那它以后一定也在最小生成树中，所以可以把它先加进去。于是可以把所有这样的边形成的连通块缩成一个点。

• 把 $[L,R]$ 中要修改的所有边修改为$\infty$，然后求一遍最小生成树。

  发现，如果一条非 $\infty$ 边不在最小生成树中，那它以后也一定不在最小生成树中，所以可以把它删去。

这样子就可以把点数和边数都缩成 $\mathcal{O}(R - L + 1)$ 级别。于是时间复杂度满足递归式 $\mathcal{T}(n) = 2\mathcal{T}(n/2) + \mathcal{O}(n \log n)$，由主定理得时间复杂度为 $\mathcal{O}(n log^2 n)$。

当 $L=R$ 时，直接修改边权，然后求一遍最小生成树并计入答案即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;
const int INF=0x3f3f3f3f;

int n,m,q;
struct Edge { int u,v,w,id; } e[30][N],d[N],t[N];
bool operator <(const Edge a,const Edge b) { return a.w<b.w; }
struct Modify { int k,d; } p[N];
int w[N],pos[N],sum[30];
ll ans[N];
int root[N];

inline int find(int x) { return x==root[x]?x:root[x]=find(root[x]); }
inline void clear(int s,Edge* e) {
    for (re int i=1;i<=s;++i)
        root[e[i].u]=e[i].u,root[e[i].v]=e[i].v;
}
inline void contraction(int& s,ll& val) {
    int top=0; clear(s,d); sort(d+1,d+s+1);
    for (re int i=1;i<=s;++i) {
        int p=find(d[i].u),q=find(d[i].v);
        if (p!=q) root[p]=q,t[++top]=d[i];
    }
    clear(top,t);
    for (re int i=1;i<=top;++i) {
        int p=find(t[i].u),q=find(t[i].v);
        if (t[i].w!=-INF&&p!=q) val+=t[i].w,root[p]=q;
    }
    top=0;
    for (re int i=1;i<=s;++i) {
        int p=find(d[i].u),q=find(d[i].v);
        if (p!=q) t[++top]=(Edge){p,q,d[i].w,d[i].id};
    }
    for (re int i=1;i<=top;++i) pos[d[i].id]=i,d[i]=t[i];
    s=top;
}
inline void reduction(int& s) {
    int top=0; clear(s,d); sort(d+1,d+s+1);
    for (re int i=1;i<=s;++i) {
        int p=find(d[i].u),q=find(d[i].v);
        if (p!=q) t[++top]=d[i],root[p]=q;
        else if (d[i].w==INF) t[++top]=d[i];
    }
    for (re int i=1;i<=top;++i) pos[d[i].id]=i,d[i]=t[i];
    s=top;
}

inline void CDQ(int L,int R,int dep,ll val) {
    if (L==R) w[p[L].k]=p[L].d; //修改
    for (re int i=1;i<=sum[dep];++i) {
        e[dep][i].w=w[e[dep][i].id];
        d[i]=e[dep][i],pos[d[i].id]=i;
    }
    if (L==R) {
        ans[L]=val; clear(sum[dep],d); sort(d+1,d+sum[dep]+1);
        for (re int i=1;i<=sum[dep];++i) {
            int p=find(d[i].u),q=find(d[i].v);
            if (p!=q) root[p]=q,ans[L]+=d[i].w;
        }
        return;
    }
    int s=sum[dep];
    for (re int i=L;i<=R;++i) d[pos[p[i].k]].w=-INF;
    contraction(s,val);
    for (re int i=L;i<=R;++i) d[pos[p[i].k]].w=INF;
    reduction(s);
    for (re int i=1;i<=s;++i) e[dep+1][i]=d[i];
    sum[dep+1]=s;
    int mid=(L+R)>>1; CDQ(L,mid,dep+1,val),CDQ(mid+1,R,dep+1,val);
}

int main() {
    n=read(),m=read(),q=read();
    for (re int i=1;i<=m;++i)
        e[0][i].u=read(),e[0][i].v=read(),e[0][i].w=w[i]=read(),e[0][i].id=i;
    for (re int i=1;i<=q;++i) p[i].k=read(),p[i].d=read();
    sum[0]=m; CDQ(1,q,0,0);
    for (re int i=1;i<=q;++i) printf("%lld\n",ans[i]);
    return 0;
}