题目链接：迷失游乐园
这道题也没有传说中的那么难写吗→_→
似乎有篇博客讲得特详细……附上链接：戳这里
如果这道题不是基环树，而就是一棵树的话，我们来考虑改怎么做。因为树上的路径只有向上、向下两种走法，于是我们可以记(down_u)表示从(u)往下走的期望长度，(up_u)表示从(u)往上走的期望长度，这就很好转移了。
显然对于一个点(u)，设它的父亲为(fa_u)，有(son_u)个孩子和(num_u)个父亲(根节点认为没有父亲)，那么显然有：
[down_u=frac{sum_{fa_v=u}down_v+dis(u,v)}{son_u}]
这就是往各个孩子走的概率相等，于是求个平均值就可以了。
然后我们接着考虑(up_u)怎么求：
[up_u=dis(fa_u,u)+frac{up_{fa_u} imes num_u+down_{fa_u} imes son_{fa_u}-down_u-dis(fa_u,u)}{son_{fa_u}-1+num_{fa_u}}]
因为我们下一步从(u)走到了(fa_u)，那么之后一步可以往下也可以向上。往上走的总和就是(up_{fa_u} imes num_u)，往下走的话由于不能走回头路，于是就用(down_{fa_u} imes son_{fa_u})减去从(u)往下的(down_u)和从(fa_u)走过来的(dis(fa_u,u))即可。由于期望相当于平均值，共有(son_{fa_u}-1+num_{fa_u})种种情况，总和除以总情况数就是期望。
于是树的情况就做完辣！接下来让我们来考虑基环树的情况。
我们可以把基环树看成一个环上面长着许多棵大大小小的树。在这种情况下，我们发现每棵树的根节点也可以往上走了，并且在环上有两种走法。为了方便接下来的计算，我们可以先把环上每个点的(down)值给求出来。我们可以对于每个点，枚举它顺时针走到哪个点，那么在这个点往它的子树走的概率我们是可以递推算出来的，并且由于我们知道了每个点的(down)值，所以知道会向下走多远，于是就可以算出顺时针走的期望了。逆时针同理。于是我们就在(O(环长^2))的时间内求出环上每个点的(up)值了。剩下的部分就是树的情况了，只不过对于每个环上的点(x)有(num_x=2)，因为有往上有两种走法。
说了这么多，最后的答案就是：[sum_{i=1}^{n}frac{up_i imes num_i+down_i imes son_i}{num_i+son_i}]
代码也不长：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 100010
using namespace std;
typedef double llg;
int n,m,du[maxn],dis[maxn],hf[maxn];//hf[u]表示u有几个父亲，环上的点认为有两个父亲
int dfn[maxn],a[maxn],la,b[maxn],fa[maxn];//a数组中存的是环上的点，b[i]存的是a[i]与a[i-1]之间的距离
int head[maxn],next[maxn<<1],to[maxn<<1],c[maxn<<1],tt;
llg dn[maxn],up[maxn],ans;//dn就是向下走的期望长度，up就是向上走的期望长度
bool vis[maxn];
int getint(){
int w=0;bool q=0;
char c=getchar();
while((c>'9'||c<'0')&&c!='-') c=getchar();
if(c=='-') c=getchar(),q=1;
while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?-w:w;
}
void link(int x,int y){
to[++tt]=y;next[tt]=head[x];head[x]=tt;
to[++tt]=x;next[tt]=head[y];head[y]=tt;
c[tt-1]=c[tt]=getint();
}
void down(int u){//求向下的期望值
int cnt=0; vis[u]=1;
for(int i=head[u],v;v=to[i],i;i=next[i])
if(!vis[v]) dis[v]=c[i],down(v),cnt++,dn[u]+=dn[v]+c[i];
if(cnt) dn[u]/=cnt; du[u]=cnt; vis[u]=0;
}
void dfs(int u,int fa){//求向上的期望值
vis[u]=1; if(fa) hf[u]=1;
if(fa>0) up[u]+=(up[fa]*hf[fa]+du[fa]*dn[fa]-dn[u]-dis[u])/(du[fa]-1+hf[fa]);
for(int i=head[u],v;v=to[i],i;i=next[i])
if(!vis[v]) up[v]+=c[i],dfs(v,u);
}
void getrt(int rt,int x){//抠环
for(int u=x;u!=fa[rt];u=fa[u])//dis[u]表示u向它的父亲走的距离
a[++la]=u,b[la+1]=dis[u],vis[u]=1,hf[u]=2;
}
void Tarjan(int u,int ff){//抠环
dfn[u]=++tt; fa[u]=ff;
for(int i=head[u],v;v=to[i],i;i=next[i])
if(!dfn[v]) dis[v]=c[i],Tarjan(v,u);
else if(dfn[v]>dfn[u]) b[1]=c[i],getrt(u,v);
}
void solve(int u,int j,int z){//在环上走
llg now=0.5,di=0;//di即为在环上走过的距离，now为当前的概率
for(int i=1;i<la;i++){
if(z==-1) di+=b[j]; j+=z;
if(j==la+1) j=1; if(j==0) j=la;
if(z==1) di+=b[j];
if(i==la-1){up[u]+=now*(di+dn[a[j]]);}
else up[u]+=now*du[a[j]]*(dn[a[j]]+di)/(du[a[j]]+1);
now/=(du[a[j]]+1);
}
}
void work(){//特殊处理环
tt=0; Tarjan(1,0);
for(int i=1;i<=la;i++) down(a[i]),vis[a[i]]=1;//先求出环上每个点向下的期望
for(int i=1,u;u=a[i],i<=la;i++) solve(u,i,1),solve(u,i,-1);//正反两种走法在环上走
for(int i=1;i<=la;i++) dfs(a[i],0);//子树内求解向上走的期望值
}
int main(){
File("park");
n=getint(); m=getint();
for(int i=1;i<=m;i++) link(getint(),getint());
if(m==n-1) down(1),dfs(1,0);
else work();
for(int i=1;i<=n;i++)
ans+=(up[i]*hf[i]+dn[i]*du[i])/(du[i]+hf[i]);
printf("%.5lf",ans/n);
return 0;
}