前言

当你立下一个宏伟的或着看似简单的目标时，你最好三思、量力而行，例如想这题、写这题。

同时，我强烈谴责高实现难度题题解不放代码的行为。

思路

首先遍历整张图，得到 dfs 树，同时将所有边分为树边和返祖边（无向图 dfs 树没有横叉边）。我们接下来去分类讨论树边和返祖边有哪些边是非法的（非法边是删掉两点后，图不联通的边，合法即为联通）。

接下来默认 dfs 树根为 $1$。

对于树边

我们处理出点 $i$ 在树上的深度 $d_i$ 和深度的 $low_i$，也即 $d_i$ 和一端在子树内，另一端深度最小值的 $\min$。

注意这里是深度，因为我们没必要用 dfs 序。

接着对于每条树边，设其连接 $x$ 和 $f_x$，$f_x$ 为 $x$ 的父亲——

如果 $f_x=1$：

删掉 $x,1$ 后图会裂为两部分联通块：第一种是 $x$ 下方的儿子的子树，第二种是 $1$ 下方除了 $x$ 以外的儿子的子树。

记 $|s_i|$ 为 $i$ 的儿子数，那么剩余联通块数必然为 $|s_x|+|s_1|-1$，如果 $|s_x|+|s_1|\le 2$，则边合法，不应计入答案，否则计入答案。

注意这个不起眼的细节，最后要考。

如果 $f_x\not=1$：

删掉 $x,f_x$ 后树会裂为 $x$ 下方儿子子树部分，$f_x$ 下方除 $x$ 以外儿子子树部分，$f_x$ 子树外部分。很明显我们要使得前两个部分与 $x$ 上方部分联通，那么就要满足以下点的 $low$ 值全部 $\le d_x-2$：

• $x$ 的所有儿子。

• $f_x$ 的所有儿子，$x$ 除外。

实现技巧：记录 $uns_i$ 为 $i$ 的一个儿子，使得其 $low$ 值超过 $d_i-1$，如果有多个则为 $-1$，如果没有则为 $0$。那么判断第二部分的可行性就是看 $uns_{f_x}$ 是否等于 $0$ 或者 $x$。

对于返祖边

注意不要在祖先后代两个地方各加一次返祖边。问就是因为我踩了雷。

通常情况：

接下来忘掉 $low$ 的存在。我们使用树上启发式合并动态维护出 $i$ 子树内所有返祖边祖先的深度构成的不可重集。

对于点 $x$，我们考虑以 $x$ 为返祖边后代端时，有哪些深度的祖先可能使这条边合法。

删掉 $x$ 和 $x$ 的一个祖先 $w$ 后，整棵树会变为三部分联通块：$x$ 的儿子子树、$w$ 靠近 $x$ 的儿子子树（但是挖掉了 $x$ 的子树）、$w$ 远离 $x$ 的儿子子树、$w$ 子树外部分。记 $w$ 靠近 $x$ 的儿子为 $w_0$。

• 首先，$w$ 远离 $x$ 的所有儿子子树都必须存在返祖边连向 $w$ 子树外部分。这个可以通过 $uns_w$ 是否为 $0$ 或者 $w_0$ 来判断。

• 满足上述条件后，如果 $w$ 靠近 $x$ 的联通块和 $w$ 外的联通块之间有返祖边连接着，那么图联通当且仅当 $x$ 的所有儿子子树到 $w_0$ 抠掉 $x$ 的子树或者 $w$ 子树外均至少有一条返祖边，人话就是 $x$ 的每个儿子子树内都存在深度 $<d_x$ 且不是 $d_w$ 的返祖边祖先。

• 满足上述条件后，如果 $w$ 靠近 $x$ 的联通块和 $w$ 外的联通块之间没有返祖边，那么不仅以上条件要满足，还需要至少一个 $x$ 的儿子同时有达到 $w_0$ 抠掉 $x$ 的子树以及 $w$ 子树外的返祖边，人话就是它内部存在深度 $\in(d_w,d_x)$ 和 $\in[1,d_w)$ 的返祖边祖先。

设 $x$ 的某个儿子 $y$ 子树内：

• 没有深度 $<d_x$ 的返祖边祖先：那么 $x$ 是没救了，全部非法排除。

• 有且仅有一个符合条件的深度：那么这个深度被删掉就成为非法的了，需要排除。

• 否则记 $<d_x$ 的深度最小为 $l$，最大为 $r$：对于深度 $\in(l,r)$ 的祖先，删掉它后 $y$ 子树就会链接起两个 $x$ 上面被切开的联通块。

然后我们对于这个点为后代的返祖边，我们检验它是否是被排除的点，以及存不存在链接两个联通块的子树，接着计算 $w_0$ 子树内和 $x$ 子树内祖先端深度 $<d_w$ 的返祖边数量想不想等，来鉴定 $x$ 到 $w$ 中间一块到上方是否有返祖边。这个可以用启发式合并或者主席树完成。

$w=1$ 且 $1$ 只有 $w_0$ 一个儿子：

据前车之鉴，我们还是要判一下根的。此时不存在 $w$ 外的联通块，也不存在 $w$ 远离 $x$ 的联通块，条件转化为了所有 $x$ 的儿子子树都与中间的一大块联通。

条件就是 $d_1=1$ 没有被排除且不是全部非法，非常简单但是坑。

总结

这里两种边有哪些合法都判断完了，但是请不要忘了我们要输出非法边数。

实现注意技巧，vector 存边记录编号，新开数组记录边种类，不要写挂启发式合并，lower_bound 和迭代器自减用好，根的情况判对，运用 $uns_i$ 减少码量，以及看清 $m$ 范围，数组不要开小。

时间复杂度 $O(m\log^2 n)$，由于有一个 $\log$ 是启发式合并，所以常数非常小，洛谷上最慢的测试点跑了 668ms。

代码

布肠，野旧 3.17KB。

#include<bits/stdc++.h>
using namespace std;

int n,m,dep[100005],fath[100005],amt[100005],gson[100005],ans;
int low[100005],unsat[100005],unsat2[100005];set<int>M;
vector<pair<int,int> >mp[100005],V[100005];
vector<int>nmp[100005];int stk[100005];
bool vis[100005],bta[300005],sing[300005],doub[300005],basc[300005];
vector<pair<int,pair<int,int> > >Q[100005];
int tr[100005],sbctr[300005];

void dfs(int x,int fa){
	fath[x]=fa;low[x]=dep[x]=dep[fa]+1;vis[x]=1;
	amt[x]=1;
	for(auto uu:mp[x]){
		int y=uu.first;if(y==fa)continue;
		if(vis[y]){
			if(dep[y]<dep[x]){
				bta[uu.second]=1;V[x].push_back(uu);low[x]=min(low[x],dep[y]);
			}
		}
		else{
			dfs(y,x);low[x]=min(low[x],low[y]);amt[x]+=amt[y];
			nmp[x].push_back(y);if(amt[y]>amt[gson[x]])gson[x]=y;
		}
	}
}

void addbit(int x,int v){
	for(;x<=n;x+=(x&-x))tr[x]+=v;
}

int querybit(int x){
	int ca=0;for(;x;x&=(x-1))ca+=tr[x];
	return ca;
}

void add(int x){
	for(auto uu:V[x])M.insert(dep[uu.first]);
	for(auto y:nmp[x])add(y);
}

void add424(int x,int v){
	for(auto uu:V[x])addbit(dep[uu.first],v);
	for(auto y:nmp[x])add424(y,v);
}

void dfsEX(int x){
	stk[dep[x]]=x;bool satis=1;set<int>s;map<int,int>t,tt;
	for(auto y:nmp[x])if(y!=gson[x]){
		dfsEX(y);set<int>::iterator itr=M.lower_bound(dep[x]);
		if(itr==M.begin())satis=0;
		else if((--itr)==M.begin())s.insert(*itr);
		else t[(*M.begin())+1]=max(t[(*M.begin())+1],(*itr)-1);
		M.clear();
	}
	if(gson[x]){
		dfsEX(gson[x]);set<int>::iterator itr=M.lower_bound(dep[x]);
		if(itr==M.begin())satis=0;
		else if((--itr)==M.begin())s.insert(*itr);
		else t[(*M.begin())+1]=max(t[(*M.begin())+1],(*itr)-1);
	}
	for(auto y:nmp[x])if(y!=gson[x])add(y);
	int mxm=0;for(auto uu:t){mxm=max(mxm,uu.second);tt[uu.first]=mxm;}
	for(auto uu:V[x]){
		int d=dep[uu.first],id=uu.second;
		if(d==1&&nmp[1].size()==1){
			doub[id]=sing[id]=satis&(s.count(1)==0);basc[id]=1;
		}
		else{
			doub[id]=sing[id]=satis&(s.count(d)==0);
			map<int,int>::iterator itr=tt.upper_bound(d);
			doub[id]&=(itr!=tt.begin()&&((--itr)->second)>=d);
			basc[id]=(unsat[uu.first]==0||unsat[uu.first]==stk[d+1]);
			Q[stk[d+1]].push_back(make_pair(d-1,make_pair(id,1)));
			Q[x].push_back(make_pair(d-1,make_pair(id,-1)));
		}
	}
	for(auto uu:V[x])M.insert(dep[uu.first]);
}

void dfsNEO(int x){
	for(auto y:nmp[x])if(y!=gson[x]){dfsNEO(y);add424(y,-1);}
	if(gson[x])dfsNEO(gson[x]);
	for(auto uu:V[x])addbit(dep[uu.first],1);
	for(auto y:nmp[x])if(y!=gson[x])add424(y,1);
	for(auto uu:Q[x])sbctr[uu.second.first]+=uu.second.second*querybit(uu.first);
}

int main(){
	cin.tie()->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		mp[x].push_back(make_pair(y,i));
		mp[y].push_back(make_pair(x,i));
	}
	dfs(1,1);
	for(int x=1;x<=n;x++){
		for(auto y:nmp[x]){
			if(low[y]>=dep[x]){if(unsat[x])unsat[x]=-1;else unsat[x]=y;}
			if(low[y]>=dep[x]-1){if(unsat2[x])unsat2[x]=-1;else unsat2[x]=y;}
		}
	}
	for(int x=2;x<=n;x++){
		if(fath[x]==1){
			if(!((nmp[x].size()==0&&nmp[1].size()==2)||(nmp[1].size()==1&&nmp[x].size()<=1)))ans++;
		}
		else if(!((unsat[fath[x]]==x||!unsat[fath[x]])&&!unsat2[x]))ans++;
	}
	dfsEX(1);dfsNEO(1);
	for(int i=1;i<=m;i++)if(bta[i]){
		if(!(basc[i]&(sbctr[i]?sing[i]:doub[i])))ans++;
	}
	cout<<ans;
	return 0;
}

花絮

早上的膜你赛原题是这道。大样例“非常”有强度，以至于一份判错树边部分根的边角料的代码能够通过所有大样例并在捆测的影响下爆零，并且让你感受到输出答案和标准答案差 $1$ 方向还不固定的绝望感。

这是一位早上十点开始写代码的同学的提交记录：