526互联

题解：【CF235D】Graph Game

发布时间 2023-04-22 18:17:42作者: LgxTpre

题目链接

根据期望的线性性，一次操作使得接下来要递归处理 \(|G|\) 个点，将这些贡献分摊到 \(|G|\) 个点上，这样我们接下来只需要计算概率。

首先考虑如果是树怎么做。操作等价于随机一个排列，顺次删掉排列中的点，并求出删掉当前点之前其所处的连通块的大小。记当前 \(x\) 为点分治中心，点对 \((x,y)\) 的贡献为 \(y\) 在 \(x\) 的点分树内部，在 \(x \to y\) 的路径上 \(x\) 第一个被删除，这个事件的概率为 \(\dfrac{1}{dis_{i,j} + 1}\)，其中 \(dis\) 表示两点间的距离。

把这个东西放在基环树上。如果点对 \((x,y)\) 在同一棵树中和上面情况相同，是平凡的。如果在不同子树中，意味着要跨过环。从环上走有两条路径，分别计算上两种走法的 \(\dfrac{1}{dis_{i,j} + 1}\) 并加起来。不过这样还会算重，容斥一下，再减去 \(x\) 和 \(y\) 到环上的距离加环上的总点数 分之一。

综上所述，我们需要预处理的东西有哪些点在环上面，哪些点在同一棵树中，同一棵树中的节点两两点对间的路径长度。然后枚举点对，如果在同一棵树中我们要求点对的 LCA，使用倍增求 LCA，总时间复杂度为 \(\mathcal O(n^2 \log n)\)。

#include<bits/stdc++.h>
#define ld long double 
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define mp make_pair
using namespace std;
 
inline int read()
{
	int s=0,w=1; char c=getchar();
	while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
	return s*w;
}
inline void write(int x,char ch)
{
	if(x<0) x=-x,putchar('-');
	static char stk[25]; int top=0;
	do {stk[top++]=x%10+'0',x/=10;} while(x);
	while(top) putchar(stk[--top]);
	putchar(ch);
	return;
}
 
namespace MyTool
{
	static const int Mod=1e9+7;
	template<typename T> inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
	inline int  Max(int a,int b)   {return (b&((a-b)>>63))|(a&(~(a-b)>>63));}
	inline int  Min(int a,int b)   {return (a&((a-b)>>63))|(a&(~(a-b)>>63));}
	template<typename T> inline void cmax(T &a,T b) {a=a>b?a:b;}
	template<typename T> inline void cmin(T &a,T b) {a=a<b?a:b;}
	inline int  Abs(int a) {return (a^(a>>63))-(a>>63);}
	inline void Madd(int &a,int b) {a=a+b>Mod?a+b-Mod:a+b;}
	inline void Mdel(int &a,int b) {a=a-b<0?a-b+Mod:a-b;}
	inline void Mmul(int &a,int b) {a=1ll*a*b%Mod;}
	inline void Mmod(int &a) {a=(a%Mod+Mod)%Mod;}
	inline int  Cadd(int a,int b)  {return a+b>=Mod?a+b-Mod:a+b;}
	inline int  Cdel(int a,int b)  {return a-b<0?a-b+Mod:a-b;}
	inline int  Cmul(int a,int b)  {return a*b%Mod;}
	inline int  Cmod(int a)  {return (a%Mod+Mod)%Mod;}
	inline int  gcd(int a,int b)   {return b?gcd(b,a%b):a;}
	inline int  qpow(int a,int b)  {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
	inline int  qmul(int a,int b)  {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
	template<typename T> inline T pow(T x)    {return x*x;}
}
using namespace MyTool;
 
inline void file()
{
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	return;
}
 
bool Mbe;
 
namespace LgxTpre
{
	static const int MAX=3010;
	static const int inf=2147483647;
	static const int INF=4557430888798830399;
	static const int mod=998244353;
	static const int bas=131;
	
	int n,x,y;
	double ans;
	
	struct edge
	{
		int nex,to;
	}e[MAX<<1];
	int head[MAX],cnt;
	inline void add(int x,int y)
	{
		e[++cnt].nex=head[x],head[x]=cnt,e[cnt].to=y;
		return;
	}
	
	int loop[MAX],deg[MAX],len,st;
	queue<int> q;
	inline void find_loop()
	{
		for(int i=1;i<=n;++i) if(deg[i]==1) q.push(i),loop[i]=1;
		while(!q.empty())
		{
			int now=q.front(); q.pop();
			for(int i=head[now];i;i=e[i].nex)
			{
				int to=e[i].to;
				if(--deg[to]==1) q.push(to),loop[to]=1;
			}
		}
		for(int i=1;i<=n;++i) loop[i]^=1,len+=loop[i],loop[i]==1?st=i:st=st;
		return;
	}
	
	int dep[MAX],col[MAX],fa[MAX][30],vis[MAX],num;
	void dfs(int now,int father,int id)
	{
		col[now]=id,fa[now][0]=father,dep[now]=dep[father]+1; 
		for(int i=1;i<=__lg(dep[now]);++i) fa[now][i]=fa[fa[now][i-1]][i-1];
		for(int i=head[now];i;i=e[i].nex)
		{
			int to=e[i].to;
			if(loop[to]||to==father) continue;
			dfs(to,now,id);
		}
		return;
	}
	inline int LCA(int x,int y)
	{
		if(dep[x]<dep[y]) Swp(x,y);
		while(dep[x]>dep[y]) x=fa[x][__lg(dep[x]-dep[y])];
		if(x==y) return x;
		for(int k=__lg(dep[x]);~k;--k) if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k];
		return fa[x][0];
	}
	void find_tree(int now)
	{
		dfs(now,0,++num),vis[now]=1;
		for(int i=head[now];i;i=e[i].nex)
		{
			int to=e[i].to;
			if(!loop[to]||vis[to]) continue;
			find_tree(to);
		}
		return;
	}
	
	inline void mian()
	{
		n=read();
		for(int i=1;i<=n;++i) x=read()+1,y=read()+1,add(x,y),add(y,x),++deg[x],++deg[y];
		find_loop(),find_tree(st);
		for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) 
			if(col[i]==col[j])
				ans+=1.0/((double)(dep[i]+dep[j]-dep[LCA(i,j)]*2+1));
			else
			{
				double T=(double)(dep[i]+dep[j]);
				double L=(double)(fabs(col[i]-col[j])-1);
				double fL=(double)(len-L-2);
				ans+=1.0/(L+T)+1.0/(fL+T)-1.0/(L+fL+T);
			}
		printf("%.15lf\n",ans);
		return;
	}
}
 
bool Med;
 
signed main()
{
//	file();
	fprintf(stderr,"%.3lf MB\n",(&Med-&Mbe)/1048576.0);
	LgxTpre::mian();  
	cerr<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
	return (0-0);
}