题解

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef map<int,multiset<int> >::iterator MSIT;
typedef set<pair<int,int > >::iterator SPIT;
const int INF=0x3f3f3f3f, maxn=200007;
int n,m,q,k;
struct edge{
    int to,nxt,val;
}e[maxn<<1];
int head[maxn];
int tot;
void addedge(int u,int v,int val){
    e[++tot].to=v;
    e[tot].nxt=head[u];
    e[tot].val=val;
    head[u]=tot;
}
namespace MST{
    struct edge1{
        int x,y,val;    
        friend bool operator <(const edge1 &a,const edge1 &b){
            return a.val<b.val; 
        }
    }G[maxn];
    int fa[maxn];
    int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
    void init(){for(int i=1;i<=n;i++)fa[i]=i;}
    void GMST(){
        init();
        sort(G+1,G+m+1);
        int cnt=0;
        for(int i=1;i<=m;i++){
            int u=G[i].x,v=G[i].y;
            int fu=find(u),fv=find(v);
            if(fu==fv)continue;
            cnt++,fa[fu]=fv;
            addedge(u,v,G[i].val);
            addedge(v,u,G[i].val);
        }
    }
}
using namespace MST;
 
struct SGT{
    int t[maxn<<2];
 
    void pushup(int x){
        t[x]=min(t[x<<1],t[x<<1|1]);
    }
    void build(int x,int l,int r){
        if(l==r){
            t[x]=INF;
            return ;
        }
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid+1,r);
        pushup(x);
    }
    void update(int id,int l,int r,int pos,int val ){
        if(l==r){
            t[id]=val;
            return ;
        }
        int mid=(l+r)>>1;
        if(pos<=mid)update(id<<1,l,mid,pos,val);
        else update(id<<1|1,mid+1,r,pos,val);
        pushup(id);
    }
}T;
multiset<pair<int,int > > best[maxn];
map<int,multiset<int > > cls[maxn];
int cl[maxn];
int f[maxn];
int w[maxn];
 
void dfs(int u,int ff){
    f[u]=ff;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==ff)continue;
        w[v]=e[i].val;
        cls[u][cl[v]].insert(w[v]);
        dfs(v,u);
    }
    for(MSIT it=cls[u].begin();it!=cls[u].end();it++){
        best[u].insert(mp(*(*it).se.begin(),(*it).fi));
    }
    if(!best[u].empty()){
        SPIT it=best[u].begin();
        if(cl[u]!=(*it).se)T.update(1,1,n,u,(*it).fi);
        else{
            it++;
            if(it==best[u].end())T.update(1,1,n,u,INF);
            else T.update(1,1,n,u,(*it).fi);
        }
    }   
}
int main(){
    scanf("%d%d%d%d",&n,&m,&k,&q);
    for(int i=1;i<=m;i++){
        int u,v,val;
        scanf("%d%d%d",&u,&v,&val);
        G[i]=(edge1){u,v,val};
    }   
    GMST();
    for(int i=1;i<=n;i++)scanf("%d",&cl[i]);
    T.build(1,1,n);
    dfs(1,0);
    while(q--){
        int u,c2;
        scanf("%d%d",&u,&c2);
        if(f[u]){
            int c1=cl[u];
            best[f[u]].erase(best[f[u]].find(mp(*cls[f[u]][c1].begin(),c1)));
            cls[f[u]][c1].erase(cls[f[u]][c1].find(w[u]));
            if(cls[f[u]][c1].empty())cls[f[u]][c1].insert(INF);
            best[f[u]].insert(mp(*cls[f[u]][c1].begin(),c1));
            if(!cls[f[u]][c2].empty())
                best[f[u]].erase(best[f[u]].find(mp(*cls[f[u]][c2].begin(),c2)));
            cls[f[u]][c2].insert(w[u]);
            best[f[u]].insert(mp(*cls[f[u]][c2].begin(),c2));
            SPIT it=best[f[u]].begin();
            if(cl[f[u]]!=(*it).se)T.update(1,1,n,f[u],(*it).fi);
            else{
                it++;
                if(it==best[f[u]].end())T.update(1,1,n,f[u],INF);
                else T.update(1,1,n,f[u],(*it).fi);
            }
        }
        if(!best[u].empty()){
            SPIT it=best[u].begin();
            if(c2!=(*it).se)T.update(1,1,n,u,(*it).fi);
            else{
                it++;
                if(it==best[u].end())T.update(1,1,n,u,INF);
                else T.update(1,1,n,u,(*it).fi);
            }
        }
        cl[u]=c2;
        printf("%d\n",T.t[1]);
    }
    return 0;
}