即将 AFO 的老年选手

题解 P6975 【[NEERC2015]Cactus Jubilee】

2021-01-02 09:03:49


广告


移动一条边等价于先删掉一条边再加入一条位置不同的边。不妨去掉位置不同的限制,最后将答案减去边数即可。

那么我们相当于要对每个断掉一条边后求出有多少种加边的方案,满足加边后是仙人掌。

分两种情况讨论:

  • 如果断掉的边是桥,那么剩下的两部分之间任意连都可以,方案数为两部分点数之积。
  • 如果断掉的边不是桥,根据 ZJOI2017 仙人掌 的结论,需要保证连边的两点路径上的边全为桥边。因此可以只保留桥边得到一个图,答案为 $\sum {sz_i-1\choose 2}$。

桥的情况可以一遍 DFS 求出,而非桥的情况似乎不好快速计算。注意到同一个环上的边断掉后保留桥边得到的连通分量相同,因此可以每次对一个环计算。这个环断掉一条边后相当于若干个连通块合并成了一个,只要找到环上的所有点,减去原来的贡献,再加上合并后的贡献即可。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

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;

int n,m;
vector<int> E[N];
ll ans=0;

int fa[N],sz[N],dfn[N],low[N],tim=0;
vector<pair<int,int>> bridge,circ;
void tarjan(int u,int f) {
    fa[u]=f,sz[u]=1,dfn[u]=low[u]=++tim;
    for (int v:E[u]) {
        if (!dfn[v]) {
            tarjan(v,u),sz[u]+=sz[v],low[u]=min(low[u],low[v]);
            if (dfn[u]<low[v])
                bridge.emplace_back(u,v),ans+=1ll*sz[v]*(n-sz[v]);
        }
        else if (v!=f) low[u]=min(low[u],dfn[v]);
    }
    for (int v:E[u])
        if (fa[v]!=u&&dfn[u]<dfn[v]) circ.emplace_back(u,v);
}

namespace dsu {
    int f[N],sz[N];
    int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
    void merge(int u,int v) {
        u=find(u),v=find(v);
        if (u!=v) sz[u]+=sz[v],f[v]=u,sz[v]=0;
    }
}

int main() {
    n=read(),m=read(); int ec=0;
    for (int i=1;i<=m;++i)
        for (int k=read()-1,u=read(),v;k;--k,u=v)
            v=read(),E[u].emplace_back(v),E[v].emplace_back(u),++ec;
    tarjan(1,0);
    for (int i=1;i<=n;++i) dsu::f[i]=i,dsu::sz[i]=1;
    for (auto i:bridge) dsu::merge(i.first,i.second);
    ll sum=0;
    for (int i=1;i<=n;++i)
        if (i==dsu::f[i]) sum+=1ll*(dsu::sz[i]-1)*(dsu::sz[i]-2)/2;
    for (auto i:circ) {
        int u=i.first,v=i.second,szc=0,cc=0; ll csum=0;
        for (int t=v;t!=fa[u];t=fa[t]) {
            int s=dsu::sz[dsu::find(t)];
            ++cc,szc+=s,csum+=1ll*(s-1)*(s-2)/2;
        }
        ans+=cc*(sum-csum+1ll*(szc-1)*(szc-2)/2);
    }
    printf("%lld\n",ans-ec);
    return 0;
}