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;
}