这是当时冬令营课上讲的题，咕咕咕到了现在
如果这题没有环套树的话，就很套路了
需要两个数组up[i]和down[i]，down[i]表示从i点第一步向下走的期望距离，up[i]表示从i点第一步向上走的期望距离，先求down，然后求up
\(down[i]=\frac{\sum_{j|son[i]}(down[j]+len(i,j))}{son[i]}\)
\(up[i]=\frac{up[fa[i]]+down[fa[i]]*son[fa[i]]-down[i]-len(fa[i],i)}{son[fa[i]]}+len(fa[i],i)\)
环套树就比较麻烦了qwqwq，但题目上告诉了我们一个环的特性：环长不超过20
那么方法也就很明了了，先将环上每个节点的子树的down处理出来，再枚举每个点，计算从这个点开始顺着环走的期望（因为不能回头，所以就是正反各搜一遍）
最后再更新每颗子树的up
最终答案就是每个节点up与down的和除以度数之和除以点数
程序中珂以再加上滚动数组，否则up和down很容易整错qwqwq
#include <bits/stdc++.h>
#define N 100005
#define db double
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline db Max(register db a,register db b)
{
return a>b?a:b;
}
struct edge{
int to,next,w;
}e[N<<1];
int head[N],cnt=0;
inline void add(register int u,register int v,register int w)
{
e[++cnt]=(edge){v,head[u],w};
head[u]=cnt;
}
int n,m,rt,tim;
int vis[N],cir[N],du[N],fa[N];
db d[N],f[N],g[N],tp[N];
db ans;
inline void dfs1(register int x)
{
vis[x]=1;
for(register int i=head[x];i;i=e[i].next)
if(!vis[e[i].to]&&!cir[e[i].to])
{
dfs1(e[i].to);
++du[x];
d[x]+=f[e[i].to]+e[i].w;
}
if(du[x])
f[x]=d[x]/(db)du[x];
if(x!=rt)
++du[x];
}
inline void dfs2(register int x)
{
vis[x]=1;
for(register int i=head[x];i;i=e[i].next)
if(!vis[e[i].to]&&!cir[e[i].to])
{
d[e[i].to]+=(d[x]-f[e[i].to]-e[i].w)/Max(1,du[x]-1)+e[i].w;
dfs2(e[i].to);
}
}
inline void dfs3(register int x)
{
vis[x]=++tim;
for(register int i=head[x],j;i;i=e[i].next)
if(e[i].to!=fa[x])
{
if(!vis[e[i].to])
{
fa[e[i].to]=x;
dfs3(e[i].to);
}
else if(vis[e[i].to]<vis[x])
for(cir[e[i].to]=1,j=x;j!=e[i].to;j=fa[j])
cir[j]=1;
}
}
inline void dfs4(register int x,register int fa)
{
bool flag=0;
g[x]=0;
for(register int i=head[x];i;i=e[i].next)
if(e[i].to!=rt&&e[i].to!=fa&&cir[e[i].to])
{
flag=1;
dfs4(e[i].to,x);
g[x]+=g[e[i].to]+e[i].w;
}
if(x==rt)
return;
int k=du[x];
k?k:++k;
if(!flag)
g[x]=d[x]/(db)k;
else
k=du[x]+1,g[x]=(g[x]+d[x])/(db)k;
}
int main()
{
n=read(),m=read();
for(register int i=1;i<=m;++i)
{
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
if(m==n-1)
{
rt=1;
dfs1(1);
memset(vis,0,sizeof(vis));
dfs2(1);
}
else
{
dfs3(1);
memset(vis,0,sizeof(vis));
for(register int i=1;i<=n;++i)
if(cir[i])
rt=i,dfs1(i);
for(register int i=1;i<=n;++i)
if(cir[i])
{
rt=i;
dfs4(i,0);
tp[i]=g[i];
}
memset(vis,0,sizeof(vis));
for(register int i=1;i<=n;++i)
if(cir[i])
du[i]+=2,d[i]+=tp[i];
for(register int i=1;i<=n;++i)
if(cir[i])
rt=i,dfs2(i);
}
for(register int i=1;i<=n;++i)
ans+=d[i]/(db)du[i];
printf("%.5lf",ans/(db)n);
return 0;
}