推荐讲解：https://www.cnblogs.com/Tunix/p/4561493.html
首先考虑树的情况，就是经典的树上概率DP。先DP出down表示从这个点向儿子走能走的期望长度，再DP出up表示向父亲走的期望长度，注意算up的时候要注意消除原先此点对父亲的down的影响。
再考虑环的情况，由于环上点不超过20个，所以怎么暴力DP都好，算出up后down用同样的方法DP即可。
概率递推式比较多，主要考虑好各种点的情况（树根，非树根，环上点，环外点，叶子）。
再注意下式子里如果某项分母为0则忽略这项。
剩下的就是心态稳健地调试了。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define For(i,x) for (int i=h[x],k; i; i=nxt[i])
typedef long long ll;
using namespace std; const int N=;
bool d[N];
int n,m,cnt,tim,tot,u,v,w,a[N],b[N],fa[N],pre[N],cf[N],dfn[N];
int son[N],h[N],nxt[N<<],to[N<<],val[N<<];
double ans,dn[N],up[N];
void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; }
int F(int x){ return x-+((x==)?tot:); } void Dn(int x,int fa){
dn[x]=;
For(i,x) if ((k=to[i])!=fa && !d[k])
son[x]++,Dn(k,x),dn[x]+=dn[k]+val[i];
if (son[x]) dn[x]/=son[x];
} void Up(int x,int c){
up[x]=c;
if (son[fa[x]]-+cf[fa[x]]) up[x]+=(son[fa[x]]*dn[fa[x]]-dn[x]-c+up[fa[x]]*cf[fa[x]])/(son[fa[x]]-+cf[fa[x]]);
For(i,x) if ((k=to[i])!=fa[x]) fa[k]=x,Up(k,val[i]);
} void dfs(int x){
dfn[x]=++tim;
For(i,x) if ((k=to[i])!=fa[x]){
if (!dfn[k]) fa[k]=x,pre[k]=val[i],dfs(k);
else if (dfn[k]>dfn[x]){
for (int t=k; t!=x; t=fa[t]) a[++tot]=t,d[t]=,cf[t]=,b[tot]=pre[t];
a[++tot]=x; d[x]=; cf[x]=; b[tot]=val[i];
}
}
} int main(){
freopen("bzoj2878.in","r",stdin);
freopen("bzoj2878.out","w",stdout);
scanf("%d%d",&n,&m);
rep(i,,m) scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
rep(i,,n) cf[i]=;
if (m==n-){
Dn(,); cf[]=;
For(i,) fa[k=to[i]]=,Up(k,val[i]);
}else{
dfs();
rep(i,,tot) Dn(a[i],);
rep(i,,tot){
int x=a[i]; double k=0.5;
for (int j=i%tot+; j!=i; j=j%tot+){
if (j%tot+!=i) up[x]+=k*(b[F(j)]+dn[a[j]]*son[a[j]]/(son[a[j]]+));
else up[x]+=k*(b[F(j)]+dn[a[j]]);
k/=son[a[j]]+;
}
k=0.5;
for (int j=F(i); j!=i; j=F(j)){
if (F(j)!=i) up[x]+=k*(b[j]+dn[a[j]]*son[a[j]]/(son[a[j]]+));
else up[x]+=k*(b[j]+dn[a[j]]);
k/=son[a[j]]+;
}
}
rep(j,,tot){
int x=a[j];
For(i,x) if (!d[k=to[i]]) fa[k]=x,Up(k,val[i]);
}
}
rep(i,,n) ans+=(up[i]*cf[i]+dn[i]*son[i])/(cf[i]+son[i]);
printf("%.5lf\n",ans/n);
return ;
}