好题
树？
考虑每个点被计算多少次
但是和当前分治中心有关系的（相当于我们把这次访问，归到这次的中心上去）
所以，f(a,b)，对于a作为中心时候，和b相连的概率
也就是两者必然分离，最后一次连在一起的时候，是否能够恰好选择a
贡献：1/(dis(x,y))
基环树？
考虑：
a，b最后一起之前断的边，在所有可能情况中，关心(a-y-b)先断的是哪一个，概率1/(x+y)，(a-z-b) 先断哪一个1/(x+z)
但是还有一种合法情况：直接断x，别的都不动。两者中会算重，减去1/(x+y+z)
所以，1/(x+y)+1/(x+z)-1/(x+y+z)
（条件概率也可以推式子证明，通分后得到同样结果）
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define ld double using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar(' ');} namespace Miracle{ const int N=3003; int n; struct node{ int nxt,to; }e[2*N]; int hd[N],cnt; void add(int x,int y){ e[++cnt].nxt=hd[x]; e[cnt].to=y; hd[x]=cnt; } int sta[N],top; bool vis[N]; bool fl; int on[N],mem[N],num; void fin(int x,int fa){ sta[++top]=x;vis[x]=1; // cout<<" xx "<<x<<" fa "<<fa<<endl; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa) continue; if(vis[y]){ if(!fl){ fl=true; int z; do{ z=sta[top--]; mem[++num]=z;on[z]=num; }while(z!=y); } } else fin(y,x); } if(sta[top]==x) sta[top--]=0; } int be[N]; int dis[N]; void dfs(int x,int fa,int rt){ be[x]=rt; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa) continue; if(on[y]) continue; dis[y]=dis[x]+1; dfs(y,x,rt); } } double ans; int rt; void sol(int x,int d){ // cout<<" x "<<x<<" "<<d;//" fa "<<fa<<" "<<d<<endl; vis[x]=1; if(x!=rt){ if(be[x]==be[rt]){ ans+=(ld)1.0/(( double)d); }else{ int a=dis[rt]+dis[x],b=abs(on[be[x]]-on[be[rt]])-1,c=num-2-b; ans+=(ld)1.0/((ld)a+b)+(ld)1.0/((ld)a+c)-(ld)1.0/((ld)a+b+c); } } for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(vis[y]) continue; sol(y,d+1); } } int main(){ rd(n);int x,y; for(reg i=1;i<=n;++i){ rd(x);rd(y); ++x;++y; add(x,y);add(y,x); } fin(1,0); for(reg i=1;i<=num;++i){ dis[mem[i]]=1; dfs(mem[i],0,mem[i]); } // cout<<"after dfs "<<endl; for(reg i=1;i<=n;++i){ memset(vis,0,sizeof vis); rt=i;sol(i,1); } ans+=n; printf("%.10lf",ans); return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/3/29 19:42:26 */