Alice and the Cactus

给?个仙?掌，每个点有 \(\frac{1}{2}\) 的概率被删除。问连通块个数的?差。

\(n \leq 5\times 10^5\)。

题解

在仙人掌这种图上，显然连通块个数=点数-(边数-环数)。

\(E(V-E+C)\) 很好算。考虑如何计算 \(E((V-E+C)^2)\)。

暴力拆开来，\(E((V-E+C)^2)=E(V^2)+E(E^2)+E(C^2)+2(E(VC)-E(VE)-E(EC))\)。

对每一项分类讨论计算即可。

https://blog.csdn.net/emmmmmmmmm/article/details/102905344

说一下时间复杂度里面的 \(O(\sum u在几个环中)\)。我们可以先把每个点看成都在一个环中，那么 \(>1\) 的部分就可以看成环之间的连边。所以时间复杂度还是 \(O(n)\)。

CO int N=5e5+10;
int n,m,pw[N];
vector<int> to[N];
int vis[N],stk[N],pos[N],idx;
vector<vector<int> > cyc;
vector<int> in[N];

void dfs(int u,int fa){
    vis[u]=1,stk[++idx]=u,pos[u]=idx;
    for(int v:to[u])if(v!=fa and vis[v]!=2){
        if(!vis[v]) dfs(v,u);
        else cyc.emplace_back(stk+pos[v],stk+idx+1);
    }
    vis[u]=2,--idx;
}

int ver(){
    int ans=mul(n,pw[1]); // coincide
    ans=add(ans,mul(n,mul(n-1,pw[2]))); // disjoint
    return ans;
}
int edge(){
    int ans=mul(m,pw[2]); // coincide
    for(int u=1;u<=n;++u)
        for(int v:to[u])if(u<v){
            int s1=m-to[u].size()-to[v].size()+1;
            int s2=to[u].size()+to[v].size()-2;
            ans=add(ans,mul(s1,pw[4])); // disjoint
            ans=add(ans,mul(s2,pw[3])); // intersect
        }
    return ans;
}
int cycle(){
    int sum=0;
    for(CO vector<int>&cir:cyc) sum=add(sum,pw[cir.size()]);
    int ans=0;
    for(CO vector<int>&cir:cyc){
        int siz=cir.size(),val=sum;
        ans=add(ans,pw[siz]); // coincide
        for(int u:cir){
            for(int c:in[u]) val=sub(val,pw[c]);
            val=add(val,pw[siz]); // subtract itself mistakenly, add back it
        }
        val=sub(val,pw[siz]);
        ans=add(ans,mul(pw[siz],val)); // disjoint
        int ano=sub(sum,add(val,pw[siz]));
        ans=add(ans,mul(ano,mul(2,pw[siz]))); // intersect
    }
    return ans;
}
int veredge(){
    int ans=0;
    for(int u=1;u<=n;++u){
        int s1=to[u].size();
        int s2=m-to[u].size();
        ans=add(ans,mul(s1,pw[2])); // intersect
        ans=add(ans,mul(s2,pw[3])); // disjoint
    }
    return ans;
}
int vercycle(){
    int sum=0;
    for(CO vector<int>&cir:cyc) sum=add(sum,pw[cir.size()]);
    int ans=0;
    for(int u=1;u<=n;++u){
        int s=0;
        for(int c:in[u]) s=add(s,pw[c]);
        ans=add(ans,s); // coincide
        ans=add(ans,mul(sub(sum,s),pw[1])); // disjoint
    }
    return ans;
}
int edgecycle(){
    int ans=0;
    for(CO vector<int>&cir:cyc){
        int siz=cir.size(),s=0;
        ans=add(ans,mul(siz,pw[siz])); // coincide
        for(int u:cir) s+=to[u].size()-2;
        ans=add(ans,mul(s,pw[siz+1])); // intersect
        ans=add(ans,mul(m-siz-s,pw[siz+2])); // disjoint
    }
    return ans;
}
int calc1(){
    int s1=add(ver(),add(edge(),cycle()));
    int s2=sub(vercycle(),add(veredge(),edgecycle()));
    return add(s1,mul(2,s2));
}

int calc2(){
    int ans=sub(mul(n,pw[1]),mul(m,pw[2]));
    for(CO vector<int>&cir:cyc) ans=add(ans,pw[cir.size()]);
    return mul(ans,ans);
}

int main(){
    read(n),read(m);
    pw[0]=1;
    for(int i=1;i<=n;++i) pw[i]=mul(pw[i-1],5e8+4);
    for(int i=1;i<=m;++i){
        int u=read<int>(),v=read<int>();
        to[u].push_back(v),to[v].push_back(u);
    }
    dfs(1,0);
    for(CO vector<int>&cir:cyc)
        for(int u:cir) in[u].push_back(cir.size());
    printf("%d\n",sub(calc1(),calc2()));
    return 0;
}

跟别人学习了一波仙人掌的处理方式。

CF1236F Alice and the Cactus

原文：https://www.cnblogs.com/autoint/p/12115083.html