[Codeforces235D]Graph Game——概率与期望+基环树+容斥

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：

Codeforces235D

题目大意：给出一棵基环树，并给出如下点分治过程，求点数总遍历次数的期望。

点分治过程：

1、遍历当前联通块内所有点

2、随机选择联通块内一个点删除掉

3、对新形成的联通块进行点分治

我们设$P(A,B)$表示当删除$A$时$A,B$连通的概率，显然以$A$为分治中心时会遍历到$B$的概率为$P(A,B)$。

那么答案就是$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}P(i,j)$。

我们先考虑树的情况：

设$A,B$路径上点数(包括$A,B$)为$n$，那么$P(A,B)=\frac{1}{n}$，我们可以用数学归纳法证明：

假设当前$A,B$所处的联通块为$G$且$G$的点数为$x$。

当$n=x$时，即$G$为从$A$到$B$的链，显然只有选$A$为下一个分治中心才能使以$A$为分治中心时会遍历到$B$，所以概率是$\frac{1}{n}$

当$x>n$时，我们假设已经证明$G$的所有包含$A,B$的子联通块的$P(A,B)=\frac{1}{n}$，那么如果这次选取的分治中心在$(A,B)$路径上，概率是$\frac{n}{x}*\frac{1}{n}=\frac{1}{x}$；如果不在$(A,B)$路径上，因为删除这次选取的分治中心后$A,B$所在联通块的$P(A,B)=\frac{1}{n}$，所以概率为$\frac{x-n}{x}*\frac{1}{n}$，两种情况概率相加为$\frac{1}{n}$。

现在再来考虑基环树的情况：

如果$(A,B)$路径不经过环，那么按树的结论解决。

如果$(A,B)$路径经过环，如下图所示。

设橙色点数量为$X$，那么要保证选$A$作为分治中心之前不选橙色点作为分治中心且蓝色点(设数量为$Y$)或绿色点(设数量为$Z$)要有一组点都不在$A$之前作为分治中心，我们分别求出保留橙色点与蓝色点和橙色点与绿色点时的概率再减掉同时保留三个颜色点的概率即为$P(A,B)$，即$P(A,B)=\frac{1}{X+Y}+\frac{1}{X+Z}-\frac{1}{X+Y+Z}$。

将基环树看作是一个环的每个点上挂着一棵树，我们$O(n^2)$枚举两个点判断是否属于一棵树中并计算两点间距离即可。

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int head[5010];
int from[5010];
int to[100010];
int nex[100010];
int dep[5010];
int q[5010];
int cnt;
int vis[5010];
int bel[5010];
int num[100010];
double ans;
int tot;
int x,y,n,m;
int f[5010][17];
void add(int x,int y,int z)
{
nex[++tot]=head[x];
head[x]=tot;
to[tot]=y;
num[tot]=z;
}
bool dfs(int x,int fa)
{
vis[x]=1;
for(int i=head[x];i;i=nex[i])
{
if(num[i]!=fa)
{
if(vis[to[i]])
{
for(int j=x;j!=to[i];j=from[j])
{
q[++cnt]=j;
}
q[++cnt]=to[i];
return true;
}
else
{
from[to[i]]=x;
if(dfs(to[i],num[i]))
{
return true;
}
}
}
}
return false;
}
void find(int x,int fa,int rt)
{
bel[x]=rt;
dep[x]=dep[fa]+1;
f[x][0]=fa;
for(int i=1;i<=15;i++)
{
f[x][i]=f[f[x][i-1]][i-1];
}
for(int i=head[x];i;i=nex[i])
{
if(to[i]!=fa&&!vis[to[i]])
{
find(to[i],x,rt);
}
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])
{
swap(x,y);
}
int d=dep[x]-dep[y];
for(int i=0;i<=15;i++)
{
if(d&(1<<i))
{
x=f[x][i];
}
}
if(x==y)
{
return x;
}
for(int i=15;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
x++,y++;
add(x,y,i);
add(y,x,i);
}
dfs(1,0);
memset(vis,0,sizeof(vis));
for(int i=1;i<=cnt;i++)
{
vis[q[i]]=1;
}
for(int i=1;i<=cnt;i++)
{
find(q[i],0,i);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(bel[i]==bel[j])
{
ans+=(double)1/(dep[i]+dep[j]-2*dep[lca(i,j)]+1);
}
else
{
int X=dep[i]+dep[j];
int Y=abs(bel[i]-bel[j])-1;
int Z=cnt-Y-2;
ans+=(double)1/(X+Y)+(double)1/(X+Z)-(double)1/(X+Y+Z);
}
}
}
printf("%.7f",ans);
}