发布时间：2024-01-25

两种并查集

模板

int find(int x){
    return par[x]==x?x:par[x]=find(par[x]);
}

种类(扩展域)并查集

开多倍空间,维护种类间的关系

带权并查集

定义$dis_i 为i到根节点的关系，实际是求dis_{fx}$

可撤销并查集

struct DSU{
    vector<int> par,siz;
    stack<int> st;
    int tot=0;
    DSU(){}
    DSU(int n){
        par.resize(n);
        siz.assign(n,1);
        iota(par.begin(),par.end(),0);
    }
    int find(int x){
        return par[x]==x?x:find(par[x]);
    }
    bool merge(int x,int y,int op){
        x=find(x),y=find(y);
        if(x==y)return false;
        if(siz[x]<siz[y])swap(x,y);
        par[y]=x;
        siz[x]+=siz[y];
        if(op){
            st.push(y);
            tot++;
        }
        return true;
    }
    void del(){
        if(!tot)return;
        tot--;
        int y=st.top();
        st.pop();
        siz[par[y]]-=siz[y];
        par[y]=y;
    }
    void back(int t=0){
        while(tot>t)del();
    }
    int size(int x){
        return siz[find(x)];
    }
};

CF891C

题意：
n个点m条边，q次询问，每次询问给多个点的编号，问是否能在同一颗最小生成树内
思路：

• 离线查询
• 对于每个询问的边排序，先按照边权排序后按照序号排序
• 如果当前的边与上一条处理的边边权不同(实际为将可撤销边变为不可撤销，避免误删)或者不在同一个查询(之前连上的可撤销边与当前边具有相同权值，删掉增加可能性)，那么就可以把之前在同一个查询的边全部撤销了
• 然后将小于当前边连接，标记为不可撤销边
• 判断两点是否连通，如果是则连接上，加入可撤销边

struct DSU{
    vector<int> par,siz;
    stack<int> st;
    int tot=0;
    DSU(){}
    DSU(int n){
        par.resize(n);
        siz.assign(n,1);
        iota(par.begin(),par.end(),0);
    }
    int find(int x){
        return par[x]==x?x:find(par[x]);
    }
    bool merge(int x,int y,int op){
        x=find(x),y=find(y);
        if(x==y)return false;
        if(siz[x]<siz[y])swap(x,y);
        par[y]=x;
        siz[x]+=siz[y];
        if(op){
            st.push(y);
            tot++;
        }
        return true;
    }
    void del(){
        if(!tot)return;
        tot--;
        int y=st.top();
        st.pop();
        siz[par[y]]-=siz[y];
        par[y]=y;
    }
    void back(int t=0){
        while(tot>t)del();
    }
};
void solve(){
    int n,m,q;
    cin>>n>>m;
    vector<array<int,3>> edge(m+1),g(m+1);
    for(int i=1;i<=m;i++){
        auto &[x,y,z]=edge[i];
        cin>>x>>y>>z;
    }
    cin>>q;
    vector<array<int,2>> tmp;
    vector<int> ans(q+1,1);
    for(int i=1;i<=q;i++){
        int k;
        cin>>k;
        while(k--){
            int y;
            cin>>y;
            tmp.push_back({i,y});
        }
    }
    g=edge;
    sort(edge.begin()+1,edge.end(),[&](auto x,auto y){return x[2]<y[2];});
    sort(tmp.begin(),tmp.end(),[&](auto x,auto y){
        if(g[x[1]][2]==g[y[1]][2])return x[0]<y[0];
        return g[x[1]][2]<g[y[1]][2];
    });
    DSU dsu(n+1);
    for(int i=0,j=1;i<tmp.size();i++){
        auto [pos,id]=tmp[i];
        if(!ans[pos])continue;
        if(i&&(tmp[i-1][0]!=tmp[i][0]||g[tmp[i-1][1]][2]!=g[tmp[i][1]][2]))dsu.back();
        while(j<=m&&edge[j][2]<g[id][2]){
            dsu.merge(edge[j][0],edge[j][1],0);
            j++;
        }
        if(dsu.find(g[id][0])==dsu.find(g[id][1])){
            ans[pos]=0;
        }
        else dsu.merge(g[id][0],g[id][1],1);
    }
    for(int i=1;i<=q;i++)cout<<(ans[i]?"YES\n":"NO\n");
}

可撤销并查集与分治应用

void dfs(int l,int r){
    if(l==r){
        //update ans
        return;
    }
    int mid=l+r>>1;
    int ts=dsu.tot;
    for(int i=l;i<=mid;i++)//add edge
    dfs(mid+1,r);
    dsu.back(ts);
    for(int mid+1;i<=r;i++)//add edge
    dfs(l,mid);
    dsu.back(ts);
}

CF1681F Unique Occurrences

题意：
给一棵树每棵树上有权值，求 $\sum_{u=1}^n \sum_{v=u+1}^n f(u,v) f(u,v)表示u到v的简单路径上出现的颜色数量$
思路：

• 可以发现对于一条边，它的贡献为断开与他相同颜色的边，两边连通块大小的乘积
• 把颜色看作一个点，可以用dfs做到连上除当前颜色的所有边