本文共 2071 字，大约阅读时间需要 6 分钟。

链接：https://ac.nowcoder.com/acm/contest/3566/E
来源：牛客网

年纪轻轻的小雀当上了国王。
小雀的王国中一共有n座城市（编号为1~n），被m条双向的高速公路连接，任意两个城市之间都可以通过若干条高速公路互相到达。
但是在小雀的王国里，经常发生自然灾害。一次突发的自然灾害会随机破坏一条高速公路，并且有可能使得某两个城市之间无法到达彼此，这样整个王国就不能继续正常运转了。小雀为此很是苦恼。
于是小雀决定再修建一条高速公路，连接某两个城市，使得下一次突发自然灾害的时候，整个王国不能继续正常运转的概率最小。但是他不知道该如何选择新高速公路所连接的两个城市。
请你帮助他选择新建高速的方案，并求出新的高速公路建成之后，突发自然灾害时，整个王国不能继续正常运转的最小概率。答案对109+7取模。
对于100%的数据，2≤ n,m ≤ 200000；
输入描述:
第一行包含两个整数n,m，表示城市的数量和现有的高速公路的数量。
接下来m行，每行包含两个整数ui，vi，表示一条高速公路所连接的两个城市的编号。
输出描述:
一行一个整数，表示最小概率。
若最小概率可以表示为P/Q，请输出P*(Q^-1)%1e9+7;
输入：
7 7
1 2
1 3
1 6
2 4
2 5
4 5
6 7
输出：
125000001

思路：为了判断那条路断了会影响王国正常运行我们可以先用tarjan缩点求出割边（因为删了割边之后国家肯定不能运行），由于只能加一条边，那么加在哪儿才能使不能运作的概率最小呢？显示是利用树的直径才能使围起来的环最大，被破坏的概率越小（tarjan缩点后肯定能构成一棵树）。于是求出树的直径后答案就是缩点后的总边数-直径/m+1，具体见代码：

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mod=1e9+7;const int maxn=2e5+1;int n,m,low[maxn],dfn[maxn],a[maxn],b[maxn],vis[maxn]={   0},mx=0,id;ll num[maxn],cnt=0,sum=0;stack<int>s;vector<int>g[maxn],G[maxn];ll quick(ll a,ll b){       ll ans=1;      a=a%mod;    while(b!=0){           if(b&1) ans=(ans*a)%mod;        b>>=1;        a=(a*a)%mod;    }    return ans;}void tarjan(int x,int fa)//tarjan缩点 {   	low[x]=dfn[x]=++cnt;	vis[x]=1;	s.push(x);	int flag=0;	for(int to:g[x])	{   		if(fa==to) 		{   			if(++flag<2) continue;		}		if(!dfn[to]) tarjan(to,x),low[x]=min(low[x],low[to]);		else if(vis[to]) low[x]=min(low[x],low[to]);	}	if(dfn[x]==low[x])	{   		int t;		++sum;		do{   			t=s.top();			num[t]=sum;			vis[t]=0;			s.pop();		}while(t!=x);	}}void dfs(int x,int fa,int deep)//求树的直径，树的直径就是树上两点的最长距离 {   	if(deep>mx) 	{   		mx=deep;		id=x;	}	for(int to:G[x]) {   		if(to==fa) continue;		dfs(to,x,deep+1);	}}int main(){       scanf("%d %d",&n,&m);    for(int i=1;i<=m;++i)    {       	int u,v;    	scanf("%d %d",&u,&v);    	g[u].push_back(v);    	g[v].push_back(u);    	a[i]=u;b[i]=v;	}	tarjan(1,0);	for(int i=1;i<=m;++i)	if(num[a[i]]!=num[b[i]]) G[num[a[i]]].push_back(num[b[i]]),G[num[b[i]]].push_back(num[a[i]]);	dfs(1,0,1);	dfs(id,0,1);	printf("%lld\n",1ll*(sum-mx)*quick(m+1,mod-2)%mod); }