CF51F - Caterpillar 题解

· · 题解

不能有重边这个条件很有趣啊。就是认为重边也算环，而且把重边定义成环确实是最合理的。那么对于每个环，你只要不把这个环上所有点并成一个点，这个环就永远存在。所以需要先 eDCC 缩点（把每个 DCC 合并成一个点），得到一个森林。

下面考虑对任意一棵树，怎么用最少的合并次数合并出一个毛毛虫。考虑最终毛毛虫的一个主干路径，那么将这个路径还原之后长度一定是不变的，也就是说不会通过合并路径上的点来造主干路径，因为这不起丝毫作用。

那现在钦定一条路径，看怎么能把所有点都压到离路径只有 1 距离。手玩一波知道最优方案是把所有不在路径上的叶子保留下来，其它点全部坍塌到路径上。这样操作次数是 n-(len+leaf-2)，其中 len 是钦定路径长度，leaf 是叶子个数。只有 len 是变量，找直径就好了（bzd 为啥这题 n 只有 2000？正好我可以抄之前写过的 eDCC 缩点 + LCA 的板子暴力枚举路径，平方对数（））。

对多个连通分量（森林里的多个树），只需要两两合并即可，操作次数 c-1，其中 c 是树的棵树。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200010,LOG_N=20;
int n,m,qu;
vector<int> nei[N],rv[N];
vector<bool> brg[N];
int dfn[N],low[N],nowdfn;
void tar(int x=1,int fa=0){//to modify
    dfn[x]=low[x]=++nowdfn;
    for(int i=0;i<nei[x].size();i++){
        int y=nei[x][i];
        if(y==fa){fa=-1;continue;}
        if(!dfn[y]){
            tar(y,x),low[x]=min(low[x],low[y]);
            if(dfn[x]<low[y])brg[x][i]=brg[y][rv[x][i]]=true;
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
int cnt;
int cid[N];
void dfs(int x=1){
    cid[x]=cnt;
    for(int i=0;i<nei[x].size();i++)if(!brg[x][i]){
        int y=nei[x][i];
        if(!cid[y])dfs(y);
    }
}
vector<int> cnei[N];
int fa[N][LOG_N],dep[N];
vector<int> cc;
void dfs0(int x){
    cc.pb(x);
    for(int i=1;i<LOG_N;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=0;i<cnei[x].size();i++){
        int y=cnei[x][i];
        if(y==fa[x][0])continue;
        fa[y][0]=x;
        dep[y]=dep[x]+1;
        dfs0(y);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=LOG_N-1;~i;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
    if(x==y)return x;
    for(int i=LOG_N-1;~i;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int main(){
    cin>>n>>m;
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        nei[x].pb(y),nei[y].pb(x);
        rv[x].pb(nei[y].size()-1),rv[y].pb(nei[x].size()-1);
        brg[x].pb(false),brg[y].pb(false);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tar(i);
    for(int i=1;i<=n;i++)if(!cid[i])cnt++,dfs(i);
    for(int i=1;i<=n;i++)for(int j=0;j<nei[i].size();j++){
        int x=nei[i][j];
        if(cid[i]!=cid[x])cnei[cid[i]].pb(cid[x]);
    }
    for(int i=1;i<=cnt;i++){
        vector<int> &v=cnei[i];
        sort(v.begin(),v.end());
        v.resize(unique(v.begin(),v.end())-v.begin());
    }
    int final=-1;
    for(int i=1;i<=n;i++)if(!dep[i]){
        dep[i]=1;
        cc.clear();
        dfs0(i);
        if(cc.size()==1)continue;
        int ans=0,leaf=0;
        for(int j=0;j<cc.size();j++)leaf+=cnei[cc[j]].size()==1;
        for(int ii=0;ii<cc.size();ii++)for(int jj=0;jj<cc.size();jj++){
            int i=cc[ii],j=cc[jj],k=lca(i,j);
            if(cnei[i].size()==1&cnei[j].size()==1&&i!=j)ans=max(ans,dep[i]+dep[j]-dep[k]-dep[fa[k][0]]+(leaf-2));
        }
        final+=-ans+1;
    }
    cout<<n+final;
    return 0;
}