[CF235D] Graph Game

Graph Game
乌克兰逃兵在线发题解。

好像要用期望去推,但是像我这种看到序列的期望题只想得到线性性的弱鸡只能感理了。
我们把点分治过程当成点分树,y 能在 x 被爆时做贡献当且仅当 y 为 x 的子树。
先考虑树的情况。
考虑把遍历 t 的次数分到单个点上发现仅当 x 为 x->y 路径上第一个被爆的点时 y 会在这时被计一次。
所以 Ans+=\(\frac{1}{dis_{i,j}+1}\)。
再考虑基环树,仅经过环的路径的算法有区别。
设环上有两条路径 l1,l2,分别按树的方法计算,算重在于 l1,l2 上的点都不在 y 前爆破 x 的贡献算了两次。
所以 Ans-=\(\frac{1}{l1+l2}\)。

#include<cstdio>
#include<vector>
#include<cmath>
#include<iostream>
using namespace std;
#define db double
const int MAXN=3002;
const int N=15;
int n,cnt,head[MAXN],fa[MAXN][N],tp[MAXN],f[MAXN],top,la[MAXN],c[MAXN],c1,de[MAXN],wz[MAXN];
bool ck,vis[MAXN];
db Ans;
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
struct ren{int nxt,to;}a[MAXN<<1];
void add(int x,int y){a[++cnt].to=y;a[cnt].nxt=head[x];head[x]=cnt;}
bool dfs(int now,int F){
	la[now]=F;
	for(int i=head[now];i;i=a[i].nxt){
		if(ck) break;
		int u=a[i].to;
		if(u==F) continue;
		int fx=Find(now),fy=Find(u);
		if(fx==fy){
			int op=now;
			while(op!=u){
				c[++c1]=op;vis[op]=1;
				op=la[op];
			}
			c[++c1]=op;vis[op]=1;
			return 1;
		}
		f[fy]=fx;
		ck|=dfs(u,now);
	}
	return ck;
}
int LCA(int x,int y){
	if(de[x]>de[y]) swap(x,y);
	for(int i=12;i>=0;i--){
		if(de[fa[y][i]]>=de[x]) y=fa[y][i];
	}
	if(x==y) return  x;
	for(int i=12;i>=0;i--){
		if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	}
	return fa[x][0];
}
void dfs1(int now,int F){
	tp[now]=top;
	for(int i=head[now];i;i=a[i].nxt){
		int u=a[i].to;
		if(vis[u]||u==F) continue;
		de[u]=de[now]+1;fa[u][0]=now;
		for(int j=1;j<=12;j++) fa[u][j]=fa[fa[u][j-1]][j-1];
		dfs1(u,now);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1,x,y;i<=n;i++){
		scanf("%d%d",&x,&y);x++;y++;add(x,y);add(y,x);f[i]=i;
	}
	dfs(1,0);
	for(int i=1;i<=c1;i++){
		top=c[i];dfs1(c[i],0);wz[c[i]]=i;
	}
	for(int x=1;x<=n;x++){
		for(int y=1;y<=n;y++){
//			if(x==y) continue;注意自己可以爆自己... 
			if(tp[x]==tp[y]){
				Ans+=1.0/(1.0*(de[x]+de[y]-2*de[LCA(x,y)]+1));continue;
			}
			int l1=de[x]+de[y]+2,l2=abs(wz[tp[x]]-wz[tp[y]])-1,l3=c1-l2-2;
			Ans+=1.0/(1.0*(l1+l2));Ans+=1.0/(1.0*(l1+l3));Ans-=1.0/(1.0*(l1+c1-2));
		}	
	}
	printf("%.7lf",Ans);
	return 0;
}