CF51F - Caterpillar 题解
chenxia25
2021-08-05 09:32:05
不能有重边这个条件很有趣啊。就是认为重边也算环，而且把重边定义成环确实是最合理的。那么对于每个环，你只要不把这个环上所有点并成一个点，这个环就永远存在。所以需要先 eDCC 缩点（把每个 DCC 合并成一个点），得到一个森林。
下面考虑对任意一棵树，怎么用最少的合并次数合并出一个毛毛虫。考虑最终毛毛虫的一个主干路径，那么将这个路径还原之后长度一定是不变的，也就是说不会通过合并路径上的点来造主干路径，因为这不起丝毫作用。
那现在钦定一条路径，看怎么能把所有点都压到离路径只有 $1$ 距离。手玩一波知道最优方案是把所有不在路径上的叶子保留下来，其它点全部坍塌到路径上。这样操作次数是 $n-(len+leaf-2)$，其中 $len$ 是钦定路径长度，$leaf$ 是叶子个数。只有 $len$ 是变量，找直径就好了（bzd 为啥这题 $n$ 只有 $2000$？正好我可以抄之前写过的 eDCC 缩点 + LCA 的板子暴力枚举路径，平方对数（））。
对多个连通分量（森林里的多个树），只需要两两合并即可，操作次数 $c-1$，其中 $c$ 是树的棵树。
```cpp
#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;
}
```