题意：
给你一张n个点n-1或n条边的带权无向图。从每个点出发一直走下去，不能重复经过某个点。问走过的路径长度的数学期望是多少？ N<=100000。图中至多只有一个环，并且环长不超过20。
题解: 首先考虑是一颗树的情况： 首先随便取一个点为根（例如1号点），做树状动规。 设点i走向它的子树的期望长度为F[i]，i的子节点为s1、s2……sk。 设D[i] = ∑( F[sj] + edge(i,sj) ) ，那么F[i] = D[i] / k。 设P[i]为i作为起点的期望长度，那么P[1]=F[1]，Du[i]是节点i的度数。 再进行一次DFS，如果y是x的子节点，P[x]已经算出。 设节点y向x走对期望的贡献是other，other=(P[x]*Du[x]-edge(x,y)-F[x])/(Du[x]-1)+edge(x,y) P[y]=(other+D[y])/Du[y] 这样通过两次DFS，就可以算出所有点的P值。 但是这个题可能是一颗基环树。 首先可以通过dfs找出这个环，如果去掉这个环，那就是一些子树构成的森林。 首先用前面提到的树形动规的方法处理这些子树，求出D和F。 然后注意到环上的点很少，我们就依次让环上的每个点作为起点计算一遍。 对于环上的点x，设calc_pre(x)为从x向环上左侧走得到的期望长度，calc_nxt(x)为从x向环上右侧走得到的期望长度。 sx为x的孩子。 那么P[x]=(∑(F[sx]+edge(x,sx)+calc_pre(x)+calc_nxt(x))/Du(x)。 其中calc_pre,calc_nxt可以O(环上点个数)复杂度求出。 于是就可以再次dfs算出所有点的P。 ans=(∑P[i])/n
/**************************************************************
Problem: 2878
User: zrts
Language: C++
Result: Accepted
Time:588 ms
Memory:10748 kb
****************************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
//by zrt
//problem:
using namespace std;
typedef long long LL;
const int inf(0x3f3f3f3f);
const double eps(1e-9);
bool oncircle[100005];
int du[100005];
int fa[100005];
int H[100005],X[200005],P[200005],tot;
double E[200005];
inline void add(int x,int y,int z){//add an edge
P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z;
}
int n,m;
double F[100005];//for son E
double D[100005];// F * |son|
double p[100005];// ans
int num[100005];// |son|
int pre[100005];
double wpre[100005];
bool type;
void treedp1(int x){//Dp the tree first
for(int i=H[x];i;i=X[i]){
if(P[i]==fa[x]||oncircle[P[i]]) continue;
fa[P[i]]=x;
treedp1(P[i]);
D[x]+=F[P[i]]+E[i];num[x]++;
}
if(num[x])
F[x]=D[x]/num[x];
else F[x]=0;
}
void treedp2(int x,double edge){//Dp the tree second | calc the P
double other;
if(!fa[fa[x]]) {
if(!type){
if(num[fa[x]]>1) other=(p[fa[x]]*(num[fa[x]]+0)-edge-F[x])/(num[fa[x]]-1)+edge;
else other=edge;
}else{
other=(p[fa[x]]*(num[fa[x]]+2)-edge-F[x])/(num[fa[x]]+1)+edge;
}
}
else other=(p[fa[x]]*(num[fa[x]]+1)-edge-F[x])/num[fa[x]]+edge;
p[x]=(other+D[x])/(num[x]+1);
for(int i=H[x];i;i=X[i]){
if(P[i]==fa[x]||oncircle[P[i]]) continue;
treedp2(P[i],E[i]);
}
}
vector<int> circle;
bool ok;
int nxt[100005];double wnxt[100005];
void findcircle(int x,int fa){
for(int i=H[x];i;i=X[i]){
if(P[i]==fa) continue;
if(pre[P[i]]){
ok=1;
int k=x;
pre[P[i]]=x;
wpre[P[i]]=E[i];
do{
oncircle[k]=1;
circle.push_back(k);
k=pre[k];
}while(k!=P[i]);
oncircle[k]=1;
circle.push_back(k);
}else{
pre[P[i]]=x;wpre[P[i]]=E[i];
findcircle(P[i],x);
if(ok) return;
}
}
}
double calc_nxt(int now,int end){
double ret=wnxt[now];
now=nxt[now];
int extra=0;
if(nxt[now]!=end) ret+=calc_nxt(now,end)/(du[now]-1);
else extra=-1;
for(int i=H[now];i;i=X[i]){
if(oncircle[P[i]]) continue;
ret+=(E[i]+F[P[i]])/(du[now]-1+extra);
}
return ret;
}
double calc_pre(int now,int end){
double ret=wpre[now];
now=pre[now];
int extra=0;
if(pre[now]!=end) ret+=calc_pre(now,end)/(du[now]-1);
else extra=-1;
for(int i=H[now];i;i=X[i]){
if(oncircle[P[i]]) continue;
ret+=(E[i]+F[P[i]])/(du[now]-1+extra);
}
return ret;
}
int main(){// the main function
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=0,x,y,z;i<m;i++){
scanf("%d%d%d",&x,&y,&z);
du[x]++;
du[y]++;
add(x,y,z);
add(y,x,z);
}
if(m==n-1){
treedp1(1);
p[1]=F[1];
for(int i=H[1];i;i=X[i]){
treedp2(P[i],E[i]);
}
double ans=0;
for(int i=1;i<=n;i++){
ans+=p[i];
}
printf("%.5f\n",ans/n);
}else{
type=1;
pre[1]=-1;
findcircle(1,-1);
for(int now=0;now<circle.size();now++){
nxt[pre[circle[now]]]=circle[now];
wnxt[pre[circle[now]]]=wpre[circle[now]];
}
for(int now=0;now<circle.size();now++){
for(int i=H[circle[now]];i;i=X[i]){
if(oncircle[P[i]]) continue;
treedp1(P[i]);
p[circle[now]]+=(F[P[i]]+E[i])/du[circle[now]];
num[circle[now]]++;
}
}
for(int now=0;now<circle.size();now++){
p[circle[now]]+=(calc_pre(circle[now],circle[now])+calc_nxt(circle[now],circle[now]))/du[circle[now]];
}
for(int now=0;now<circle.size();now++){
for(int i=H[circle[now]];i;i=X[i]){
if(oncircle[P[i]]) continue;
fa[P[i]]=circle[now];
treedp2(P[i],E[i]);
}
}
double ans=0;
for(int i=1;i<=n;i++){
ans+=p[i];
}
printf("%.5f\n",ans/n);
}
return 0;
}