题解 P2081 【[NOI2012]迷失游乐园】
题解：考虑只有一棵树，那么down[x]和up[x]分别表示向上走和向下走的期望，然后先dfs一遍求down，down[i]=sigma(down[j]+len[i][j])/dui，也就是期望加起来再加上边的长度再除以总情况数。
然后再求up[x]。up[x]=len[fa[x]][x]+(up[fa[x]]+down[fa[x]]du[fa[x]]-down[x]-len[fa[x]][x])/du[fa[x]]。首先我们要走x到父亲的一段，然后再加上父亲的up+父亲的down父亲的度数，但是这样会把x子树算上，所以我们要减去down[x]和len[fa[x]][x]，最后这个整体再除以总数（也就是乘概率），就是up[x]。
那么最后所有节点的ans除以自己的度数（也就是乘概率），再全部加起来除以n，就是最后的答案了。
但是我们有一个环该怎么办呢。
首先这个环导致树变成了len(环)个小树+一个大环，所以我们可以直接对所有小树求down，up就比较麻烦了，我们先对环求出来g数组，表示从这个点开始走的期望，因为环的大小很小，所以我们枚举rt，然后直接dp一遍，g[i]=(g[to[x]]+len[to[x]][x])/(du[x]+1)，算完之后，我们再把down计入到贡献中，直接加权即可，但是要注意度数为0的情况，要强制置1。如果下一步就走到了rt，那么我们就不要把g计算到贡献中，因为我们钦定了rt，不能出现走回去的情况；如果当前点就是rt，那么不要计算down的贡献直接return，因为现在我们直接就钦定了up是往rt走的。
算完g和down对答案的贡献之后，我们把环上所有的du都+=2，因为环上有两个出边（前面不加是因为计算的是down的贡献，而g不需要度数来计算），然后我们枚举环上每个点，进行up的计算。
具体看代码吧。
自带大常数（逃
#include <bits/stdc++.h>
using namespace std;
struct nod{int to;double len;};
vector<nod>e[100005];
int x,y,z,n,m,xi,yi,wi,cir[100005],vis[100005],fa[100005],du[100005],rt,tim;
double f[100005],d[100005],tp[100005],g[100005],ans;
void dfs1(int x)
{
vis[x]=1;
for(int i=0;i<e[x].size();i++)
if(!vis[e[x][i].to]&&!cir[e[x][i].to])
dfs1(e[x][i].to),du[x]++,d[x]+=f[e[x][i].to]+e[x][i].len;
if(du[x]) f[x]=d[x]/(double)du[x];
if(x!=rt) du[x]++;
}
void dfs2(int x)
{
vis[x]=1;
for(int i=0;i<e[x].size();i++)
if(!vis[e[x][i].to]&&!cir[e[x][i].to])
d[e[x][i].to]+=(d[x]-f[e[x][i].to]-e[x][i].len)/max(1,du[x]-1)+e[x][i].len,dfs2(e[x][i].to);
}
void dfs3(int x)
{
vis[x]=++tim;
for(int i=0,j;i<e[x].size();i++)
if(e[x][i].to!=fa[x])
{
if(!vis[e[x][i].to]) fa[e[x][i].to]=x,dfs3(e[x][i].to);
else if(vis[e[x][i].to]<vis[x]) for(cir[e[x][i].to]=1,j=x;j!=e[x][i].to;j=fa[j]) cir[j]=1;
}
}
void dfs4(int x,int fa)
{
bool flag=0;g[x]=0;
for(int i=0;i<e[x].size();i++)
if(e[x][i].to!=rt&&e[x][i].to!=fa&&cir[e[x][i].to])
flag=1,dfs4(e[x][i].to,x),g[x]+=g[e[x][i].to]+e[x][i].len;
if(x==rt) return;
int k=du[x];k?k:k++;
if(!flag) g[x]=d[x]/(double)k;
else k=du[x]+1,g[x]=(g[x]+d[x])/(double)k;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d%d",&x,&y,&z),e[x].push_back((nod){y,z}),e[y].push_back((nod){x,z});
if(m==n-1) rt=1,dfs1(1),memset(vis,0,sizeof vis),dfs2(1);
else
{
dfs3(1);memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++) if(cir[i]) rt=i,dfs1(i);
for(int i=1;i<=n;i++) if(cir[i]) rt=i,dfs4(i,0),tp[i]=g[i];
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) if(cir[i]) du[i]+=2,d[i]+=tp[i];
for(int i=1;i<=n;i++) if(cir[i]) rt=i,dfs2(i);
}
for(int i=1;i<=n;i++) ans+=d[i]/(double)du[i];
printf("%.5lf\n",ans/(double)n);
}