CF235D

从 loj6240 来的，是仙人掌强化版。建议大家都尝试一下。

本篇题解将从树的做法一直讲到仙人掌的。

树

题目让我们求基环树，但是我没写过基环树上点分治怎么办？于是先考虑树的情况。

我们一定会以某种顺序删完所有点，所以我们可以设法求出所有点被删时，它所在的连通块的期望大小。更进一步，根据期望的线性性，我们可以算出一个点 $x$ 被删时，另一个点 $y$ 对连通块大小的期望贡献，其实也就是 $x$ 和 $y$ 联通的概率之和。

这是一个经典的问题，有点类似 CF280C 的思路。如果删 $x$ 时，$y$ 仍然与其联通，当且仅当 $x$ 到 $y$ 的链上所有点都还没被删。所以这个点对 $(x,y)$ 的贡献即为 $\frac{1}{dis(x,y)}$。全部 $(x,y)$ 求和即为答案。

基环树

我们现在已经会了树，那么基环树就可以用类似的思路。

此时，每个 $(x,y)$ 会有两种情况：

• $(x,y)$ 路径不经过环。

这样和树的情况无异。

• $(x,y)$ 路径经过环。

此时 $x$ 到 $y$ 就会有两条路径，我们把其中必须经过的点的集合记作 $A$，然后环上两边选一边走，两个点集分别记作 $B,C$。我们会发现，$A\cup B$ 都没被删，则 $x,y$ 联通，同理 $A\cup C$ 也一样。但是此时如果 $A\cup B\cup C$ 都没被删，则会有重复的贡献。

于是考虑一个简单容斥，去掉 $A\cup B\cup C$ 都没被删的贡献即 $\frac{1}{|A|+|B|+|C|}$。所以最后 $x,y$ 联通的概率就是 $\frac{1}{|A|+|B|}+\frac{1}{|A|+|C|}-\frac{1}{|A|+|B|+|C|}$。

实现上，可以直接建出圆方树（也方便仙人掌情况）然后固定 $x$ dfs。时间复杂度 $O(n^2)$。

code：

int n,dis[N][N];
int cur,top,st[N],dfn[N],low[N];
int k,siz[N];
double ans;
vector<int> E[N],g;
int tot,head[N];
struct node{
	int to,nxt;
}e[N<<1];
il void add(int u,int v){
	e[++tot]={v,head[u]},head[u]=tot;
}
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
void tarjan(int u){
	dfn[u]=low[u]=++cur;
	st[++top]=u;
	for(int v:E[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				k++;
				do{
					int v=st[top];
					add(v,k),add(k,v);
					siz[k]++;
				}while(st[top--]!=v);
				add(u,k),add(k,u);
				siz[k]++;
				if(siz[k]>2){
					go(i,k){
						g.eb(e[i].to);
					}
				}
			}
		}else{
			low[u]=min(low[u],dfn[v]);
		}
	}
}
void dfs(int u,int f,int x,int y,int z,int w){
	if(u<=n){
		x++,ans+=1.0/x,z++;
		if(y>=0){
			y++,ans+=1.0/y-1.0/z;
		}
	}
	go(i,u){
		int v=e[i].to;
		if(v==f){
			continue;
		}
		if(v<=n){
			if(siz[u]>2){
				dfs(v,u,x+dis[w][v]-1,x+siz[u]-dis[w][v]-1,z+siz[u]-2,w);
			}else{
				dfs(v,u,x,y,z,w);
			}
		}else{
			dfs(v,u,x,y,z,u);
		}
	}
}
void Yorushika(){
	scanf("%d",&n),k=n;
	rep(i,1,n){
		int u,v;scanf("%d%d",&u,&v);
		u++,v++;
		E[u].eb(v),E[v].eb(u);
	}
	rep(i,1,n){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	rep(i,0,(int)g.size()-1){
		rep(j,0,(int)g.size()-1){
			dis[g[i]][g[j]]=abs(i-j);
		}
	}
	rep(i,1,n){
		dfs(i,0,0,-1,0,0);
	}
	printf("%.8lf\n",ans);
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}

仙人掌

最后考虑仙人掌。仙人掌版本增加了很多的环，于是尝试从一个环的容斥拓展到多个环的容斥。

发现每对 $x,y$ 的路径上都会出现多个环，每个环我们都能类似基环树，选择其中的一半（即上面的 $B,C$），或者整个环全选，钦定选定的点都不能删。如果全选，根据基环树的做法推断，我们需要将容斥系数 $\times -1$。

于是，还是先固定 $x$，考虑一个 dp：设 $dp_{u,i}$ 表示当前 $y=u$ 且钦定不能删的点有 $i$ 个的情况数。转移也就是选 $B,C,B\cup C$ 中的一个。要注意 $A$ 也就是一定会经过的点的处理。

最后答案即为 $\sum dp_{u,i}\times\frac{1}{i}$。时间复杂度 $O(n^3)$。

code：

int n,m,dp[N][N],dis[N][N],inv[N];
int cur,top,st[N],dfn[N],low[N];
int k,siz[N];
int ans=0;
vector<int> E[N];
int tot,head[N];
struct node{
	int to,nxt;
}e[N<<1];
il void add(int u,int v){
	e[++tot]={v,head[u]},head[u]=tot;
}
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
void tarjan(int u){
	dfn[u]=low[u]=++cur;
	st[++top]=u;
	for(int v:E[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				k++;
				do{
					int v=st[top];
					add(v,k),add(k,v);
					siz[k]++;
				}while(st[top--]!=v);
				add(u,k),add(k,u);
				siz[k]++;
			}
		}else{
			low[u]=min(low[u],dfn[v]);
		}
	}
}
void dfs(int u,int f,int w){
	if(u<=n){
		drep(i,m,1){
			dp[u][i]=dp[u][i-1];
		}
		dp[u][0]=0;
		rep(i,0,m){
			ans=Mod(ans,1ll*dp[u][i]*inv[i]%mod);
		}
	}
	go(i,u){
		int v=e[i].to;
		if(v==f){
			continue;
		}
		if(v<=n){
			rep(j,0,m){
				dp[v][j+dis[w][v]-1]=Mod(dp[v][j+dis[w][v]-1],dp[w][j]);
				dp[v][j+siz[u]-dis[w][v]-1]=Mod(dp[v][j+siz[u]-dis[w][v]-1],dp[w][j]);
				dp[v][j+siz[u]-2]=Mod(dp[v][j+siz[u]-2],mod-dp[w][j]);
			}
		}
		dfs(v,u,u<=n?u:w);
	}
}
void Yorushika(){
	scanf("%d%d",&n,&m),k=n;
	mems(dis,0x3f);
	rep(i,1,m){
		int u,v;scanf("%d%d",&u,&v);
		E[u].eb(v),E[v].eb(u);
		dis[u][v]=dis[v][u]=1;
	}
	rep(k,1,n){
		rep(i,1,n){
			rep(j,1,n){
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	rep(i,1,n){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	inv[1]=1;
	rep(i,2,m){
		inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
	}
	rep(i,1,n){
		mems(dp,0),dp[i][0]=1;
		dfs(i,0,0);
	}
	printf("%d\n",ans);
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}