新的做法

esgojg · 2025-08-23 15:48:57 · 题解

最短路为 MST 上一条边的结论别的题解已经证明了，这里不再赘述\ 有这么一个结论：在 Kruskal 算法合并 u,v 两个点时，你可以连 u 所在连通分量和 v 所在连通分量任意两个点\ 证明：连边有两个用，一是将两个连通分量连起来，二是有权值\ 第一个作用显然不影响，这里考虑第二个\ 如果要用到 (u,v) 边的权值，则由 Kruskal 算法的性质，u,v 子树的所有边两端颜色都相同\ 所以 u 所在连通分量每个点颜色相同，v 同理\ 此时连哪两个点都一样了

所以直接合并时连接两个子树的任一度数不大于 1 的点\ 由数学归纳法，合并后子树永远是一条链，用一个数组维护链的端点即可

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=4e5+5;
int n,m,k,q,fa[N],col[N],lst[N];
vector<pair<int,int> >G[N];
multiset<int>ans;
struct edge{
    int u,v,w;
    bool operator<(edge b){
        return w<b.w;
    }
}e[M];
int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
int main(){
    cin>>n>>m>>k>>q;
    for(int i=1,u,v,w;i<=m;i++)cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1);
    for(int i=1;i<=n;i++)cin>>col[i],fa[i]=lst[i]=i;
    for(int i=1;i<=m;i++){
        auto[u,v,w]=e[i];
        int fu=find(u),fv=find(v);
        if(fu==fv)continue;
        fa[fu]=fv;
        G[lst[fu]].push_back({lst[fv],w});
        G[lst[fv]].push_back({lst[fu],w});
        lst[fv]=fu;
    }
    for(int u=1;u<=n;u++)
        for(auto[v,w]:G[u])
            if(u<v&&col[u]!=col[v]) ans.insert(w);
    while(q--){
        int u,k;cin>>u>>k;
        for(auto [v,w]:G[u])
            if(col[u]==col[v]&&k!=col[v]) ans.insert(w);
            else if(col[u]!=col[v]&&k==col[v])ans.erase(ans.find(w));
        printf("%d\n",*ans.begin());
        col[u]=k;
    } 
    return 0;
}