题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2878
很好的树上概率题的思路，就是分成up和down。
代码中有众多小细节。让我弃疗好几天的致命小细节是dfs1里面那个sum要定义成double的！……
#include<iostream>
#include<cstdio>
#include<cstring>
#define db double
using namespace std;
const int N=1e5+;
int n,m,head[N],xnt,f[N],son[N],stack[N],top;
db down[N],up[N];
bool vis[N],in[N],flag;
struct Edge{
int next,to,w;
Edge(int n=,int t=,int w=):next(n),to(t),w(w) {}
}edge[N<<];
void add(int x,int y,int z)
{
edge[++xnt]=Edge(head[x],y,z);head[x]=xnt;
edge[++xnt]=Edge(head[y],x,z);head[y]=xnt;
}
void dfs1(int cr,int fa)
{
double sum=;//double
for(int i=head[cr],v;i;i=edge[i].next)
if((v=edge[i].to)!=fa&&!in[v])
{
son[cr]++;dfs1(v,cr);
sum+=down[v]+edge[i].w;//+edge[i].w!!
}
if(son[cr])down[cr]=sum/son[cr];
}
void dfs2(int cr,int fa,int d)
{
if(fa)//判断if(fa)!!
{
f[cr]=;//环上的点fa是0
up[cr]=d; //////如果放在下面的式子里，就少加了d ——但是怎么会有!(son[fa]-1+f[fa])的情况呢？ //fa只有一条边的时候！
if(son[fa]-+f[fa])up[cr]+=(down[fa]*son[fa]-d-down[cr]+up[fa]*f[fa])/(son[fa]-+f[fa]);
// printf("cr=%d up=%.5lf(upfa=%.5lf)\n",cr,up[cr],up[fa]);
} //环上的点不求up，已在solve2里求过
for(int i=head[cr],v;i;i=edge[i].next)
if((v=edge[i].to)!=fa&&!in[v])dfs2(v,cr,edge[i].w);
}
void tarjan(int cr,int fa)
{
stack[++top]=cr;vis[cr]=;
for(int i=head[cr],v;i;i=edge[i].next)
if((v=edge[i].to)!=fa)
{
if(vis[v])
{
while(stack[top]!=v)in[stack[top--]]=;//!=v不是!=cr
in[stack[top--]]=;flag=;return;
}
else tarjan(v,cr);
if(flag)return;
}
top--;/////////
}
void solve(int root,int cr,int fa,double g,int d)/////自己的写法，判cr!=root！！
{
for(int i=head[cr],v;i;i=edge[i].next)
if(in[v=edge[i].to]&&v!=fa)
{
if(v==root)
{
up[root]+=g*(down[cr]+d);//
// printf("root=%d cr=%d up=%.5lf(down[cr]=%.5lf g=%.5lf)\n",root,cr,up[root],down[cr],g);
return;
}
if(cr!=root)up[root]+=g*(down[cr]+d)*son[cr]/(son[cr]+);//先+d再乘son[cr]
// printf("root=%d cr=%d up=%.5lf(down[cr]=%.5lf son[cr]=%d g=%.5lf)\n",root,cr,up[root],down[cr],son[cr],g);
if(cr==root)solve(root,v,cr,g/,d+edge[i].w); //son可能有多个
else solve(root,v,cr,g/(son[cr]+),d+edge[i].w);
}
}
int main()
{
scanf("%d%d",&n,&m);int x,y,z;
if(n==)
{
printf("0.00000");return ;
}
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);add(x,y,z);
}
if(m==n-)dfs1(,),dfs2(,,);
else{
tarjan(,);
for(int i=;i<=n;i++)if(in[i])dfs1(i,);
for(int i=;i<=n;i++)if(in[i])solve(i,i,,,);///!!!!!!!!
for(int i=;i<=n;i++)if(in[i])f[i]=,dfs2(i,,);
}
// for(int i=1;i<=n;i++)printf("i=%d up=%.5lf down=%.5lf\n",i,up[i],down[i]);
double sum=;
for(int i=;i<=n;i++)sum+=(down[i]*son[i]+up[i]*f[i])/(son[i]+f[i]);
printf("%.5lf",sum/n);
return ;
}