BZOJ2878: [Noi2012]迷失游乐园

游乐园"/>

BZOJ2878: [Noi2012]迷失游乐园

BZOJ2878: [Noi2012]迷失游乐园

树形Dp

---

题解：

orz orz orz orz
ORZ Tunix ORZ
orz orz orz orz

---

简单写一下，怕自己忘了。。。

先考虑没有环的情况。

令点1为树根，设 down[i] $down[i]$表示从i开始向下走的期望步数， up[i] $up[i]$表示往上走的。

down[i] $down[i]$的计算很简单：

down[i]=∑(down[j]+w[i][j])son[i] $$down[i]=\frac{ \sum{ (down[j]+w[i][j]) } } {son[i]}$$

考虑 up[i] $up[i]$，点i走到父亲f后，可以顺着其他的儿子向下走，也可以继续往上。所以：

up[i]=len[i][f]+down[f]∗son[f]−down[i]−len[f][i]+up[f]son[f]−1+1 $$up[i]=len[i][f]+\frac{down[f]*son[f]-down[i]-len[f][i]+up[f]}{son[f]-1+1}$$

最后，以每个点为出发点统计答案：

ans=∑ni=1down[i]∗son[i]+up[i]son[i]+1n $$ans=\frac{\sum_{i=1}^{n}{\frac{down[i]*son[i]+up[i]}{son[i]+1}}}{n}$$

---

考虑环呢？注意最多只有一个环。

不在环上的点一样算，环上的down也一样算。

环上的点的up值其实就是沿着环走到其他的任意一个环上的点，然后再沿外向树向下走的期望长度。

这一段直接看代码吧。

for(int i=1;i<=tot;i++){int now=cir[i];double k=1;for(int x=nxt[now];x!=now;x=nxt[x]){if(nxt[x]!=now)up[now]+=k*(len[id[pre[x]]][id[x]]+down[x]*son[x]/(son[x]+1));elseup[now]+=k*(len[id[pre[x]]][id[x]]+down[x]);k/=(son[x]+1);}k=1;for(int x=pre[now];x!=now;x=pre[x]){if(pre[x]!=now)up[now]+=k*(len[id[nxt[x]]][id[x]]+down[x]*son[x]/(son[x]+1));elseup[now]+=k*(len[id[nxt[x]]][id[x]]+down[x]);k/=(son[x]+1);}up[now]/=2;
}

两个并列的循环分别是顺时针、逆时针，最后/2。k是走到这个点的概率，每次乘以 1son[x]+1 $1 \over son[x]+1$.

另外环上的点算是有两个父亲，于是定义 pa[i] $pa[i]$表示i的父亲个数，则 up[i] $up[i]$的式子化为：

up[i]=len[i][f]+down[f]∗son[f]−down[i]−len[f][i]+up[f]∗fa[i]son[f]−1+pa[i] $$up[i]=len[i][f]+\frac{down[f]*son[f]-down[i]-len[f][i]+up[f]*fa[i]}{son[f]-1+pa[i]}$$

---

注意除0！

Code：

#include <iostream>
#include <cstring>
#include <cstdio>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
const int N = 100005;int n,m,flag,tot; double up[N],down[N]; bool bo[N];
int len[21][21],cir[21],id[N],pre[N],nxt[N],fa[N],son[N];struct Edge{int to,next,w;
} e[N*2];
int head[N], ec=0;
void add(int a,int b,int w){ec++; e[ec].to=b; e[ec].w=w;e[ec].next=head[a]; head[a]=ec;
}void findcir(int u,int f){bo[u]=true;for(int i=head[u];i;i=e[i].next){int v=e[i].to; if(v==f) continue;if(bo[v]){ flag=v; return; }findcir(v,u);if(flag>0){if(flag==u) flag=-1;return;}if(flag==-1) break;}bo[u]=false;
}void dfscir(int u,int f){if(id[u]) return;id[u]=++tot; cir[tot]=u; fa[u]=2;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v==f) continue;if(!bo[v]) continue;nxt[u]=v; pre[v]=u;dfscir(v,u);len[id[u]][id[v]]=len[id[v]][id[u]]=e[i].w;break;}
} void dfsdown(int u,int f){for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v==f || bo[v]) continue;fa[v]=1; dfsdown(v,u);son[u]++; down[u]+=down[v]+e[i].w;}if(son[u]) down[u]/=son[u];
}void dfsup(int u,int f,int w){up[u]=w;if(son[f]+fa[f]>1){up[u]+=(up[f]*fa[f]+son[f]*down[f]-down[u]-w)/(son[f]+fa[f]-1);}for(int i=head[u];i;i=e[i].next){if(e[i].to!=f) dfsup(e[i].to,u,e[i].w);}
}int main(){freopen("a.in","r",stdin);freopen("a.out","w",stdout);cin>>n>>m; int a,b,w;for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&w);add(a,b,w); add(b,a,w);}if(m<n){dfsdown(1,0);for(int i=head[1];i;i=e[i].next)dfsup(e[i].to,1,e[i].w);}else{findcir(1,0);//      for(int i=1;i<=n;i++) if(bo[i]) D(i); E;for(int i=1;i<=n;i++){if(bo[i]){ dfscir(i,0); break; }}//      for(int i=1;i<=n;i++){ if(bo[i]){ D(i); D(pre[i]); D(nxt[i]); E; } }for(int i=1;i<=tot;i++){ dfsdown(cir[i],0); }for(int i=1;i<=tot;i++){int now=cir[i];double k=1;for(int x=nxt[now];x!=now;x=nxt[x]){if(nxt[x]!=now)up[now]+=k*(len[id[pre[x]]][id[x]]+down[x]*son[x]/(son[x]+1));elseup[now]+=k*(len[id[pre[x]]][id[x]]+down[x]);k/=(son[x]+1);}k=1;for(int x=pre[now];x!=now;x=pre[x]){if(pre[x]!=now)up[now]+=k*(len[id[nxt[x]]][id[x]]+down[x]*son[x]/(son[x]+1));elseup[now]+=k*(len[id[nxt[x]]][id[x]]+down[x]);k/=(son[x]+1);}up[now]/=2;}for(int j=1;j<=tot;j++){for(int i=head[cir[j]];i;i=e[i].next)if(!id[e[i].to]) dfsup(e[i].to,cir[j],e[i].w);}}//  for(int i=1;i<=n;i++) D(down[i]), E;
//  for(int i=1;i<=n;i++) D(up[i]), E;double ans=0;for(int i=1;i<=n;i++) ans+=(up[i]*fa[i]+down[i]*son[i])/(fa[i]+son[i]);printf("%.5f\n",ans/n);
}