洛谷2081 bzoj2878 NOI2012 迷失游乐园 期望+基环树dp

游乐园 期望+基环树dp"/>

洛谷2081 bzoj2878 NOI2012 迷失游乐园 期望+基环树dp

题目链接
题意：给你一棵无根树或基环树，求从任意一点出发，不能重复经过某个点，经过的路径的期望长度。
题解：
首先考虑树的情况。由于是无根树，我们在树形dp时通常会转为有根树。转为有根树之后我们发现，对于每个点，从它出发不能重复经过任何一个点的路径的期望长度与从它出发向子树走的期望和向父节点走的期望有关。我们设节点 x x $x$向子树走得到的期望长度是down[x]" role="presentation" style="position: relative;">down[x]down[x]$down[x]$，向父节点走的得到期望长度是 up[x] u p [ x ] $up[x]$， x x $x$在有根树上的儿子个数是son[x]" role="presentation" style="position: relative;">son[x]son[x]$son[x]$， hf[x] h f [ x ] $hf[x]$表示 x x $x$向上走有多少个可以走的父节点（在基环树的情况下环上的点看作有两个父节点）。那么答案就是son[x]∗down[x]+up[x]son[x]+hf[x]" role="presentation" style="position: relative;">son[x]∗down[x]+up[x]son[x]+hf[x]son[x]∗down[x]+up[x]son[x]+hf[x]$\frac{son[x]*down[x]+up[x]}{son[x]+hf[x]}$。我们发现，要求 up[x] u p [ x ] $up[x]$需要先求出 down[x] d o w n [ x ] $down[x]$，那么我们就用树形dp常用的两遍dfs的方法分别求出 down[x] d o w n [ x ] $down[x]$和 up[x] u p [ x ] $up[x]$。我们发现，

down[x]=∑y∈son[x](down[y]+dis[x][y])son[x] d o w n [ x ] = ∑ y ∈ s o n [ x ] ( d o w n [ y ] + d i s [ x ] [ y ] ) s o n [ x ] $$down[x]=\frac{\sum_{y\in son[x]}(down[y]+dis[x][y])}{son[x]}$$ 所以我们要从叶子向根dp。处理完了 down[x] d o w n [ x ] $down[x]$之后我们再来算 up[x] u p [ x ] $up[x]$。我们设点 x x $x$的父节点为fa[x]" role="presentation" style="position: relative;">fa[x]fa[x]$fa[x]$，那么有 up[x]=down[fa[x]]∗son[fa[x]]−down[x]−dis[fa[x]][x]+up[fa[x]]son[fa[x]]−1+hf[fa[x]] u p [ x ] = d o w n [ f a [ x ] ] ∗ s o n [ f a [ x ] ] − d o w n [ x ] − d i s [ f a [ x ] ] [ x ] + u p [ f a [ x ] ] s o n [ f a [ x ] ] − 1 + h f [ f a [ x ] ] $$up[x]=\frac{down[fa[x]]*son[fa[x]]-down[x]-dis[fa[x]][x]+up[fa[x]]}{son[fa[x]]-1+hf[fa[x]]}$$ 分母的 −1 − 1 $-1$是因为向上走要减去从 fa[x] f a [ x ] $fa[x]$走到 x x $x$的情况，+hf[fa[x]]" role="presentation" style="position: relative;">+hf[fa[x]]+hf[fa[x]]$+hf[fa[x]]$是要加上从 fa[x] f a [ x ] $fa[x]$走到它的父节点（ fa[fa[x]] f a [ f a [ x ] ] $fa[fa[x]]$）的情况。
分子是由父节点向其他子节点的情况（向下的总期望减去走当前 x x $x$的期望）加上再继续往上走的期望。
我们发现up[x]" role="presentation" style="position: relative;">up[x]up[x]$up[x]$是需要从根向叶子节点dp的。
我们算出每个点的 down[x] d o w n [ x ] $down[x]$和 up[x] u p [ x ] $up[x]$之后，答案就是 ∑ni=1down[i]∗son[i]+up[i]son[i]+hf[i]n ∑ i = 1 n d o w n [ i ] ∗ s o n [ i ] + u p [ i ] s o n [ i ] + h f [ i ] n $$\frac{\sum_{i=1}^{n}\frac{down[i]*son[i]+up[i]}{son[i]+hf[i]}}{n}$$
这样我们就解决了树的情况，下面考虑环的情况。
首先我们先找出哪些点在环上，然后我们把这个环看作有根树的根，这样就可以用类似的方法算出所有点的 down d o w n $down$。由于算 up[x] u p [ x ] $up[x]$时要从根到叶子dp，所以我们要先算出环上每个点的 up u p $up$。我们考虑 up[x] u p [ x ] $up[x]$的含义是从 x x $x$向父节点走的期望步数，那么对于环上的点，它们可以有顺时针和逆时针走两种选择，所以它们的父节点数是hf[x]=2" role="presentation" style="position: relative;">hf[x]=2hf[x]=2$hf[x]=2$（ x x $x$在环上）。那么我们就分顺时针和逆时针两种情况来算。首先顺时针和逆时针的概率都是0.5" role="presentation" style="position: relative;">0.50.5$0.5$，然后每到达环上一个没到过的点，到达之后有 son[x]+1 s o n [ x ] + 1 $son[x]+1$种选择，也就是在达到的点向子树走的情况和继续在环上转的情况。那么有 son[x]son[x]+1 s o n [ x ] s o n [ x ] + 1 $\frac{son[x]}{son[x]+1}$的概率往子树走，有 1son[x]+1 1 s o n [ x ] + 1 $\frac{1}{son[x]+1}$的概率继续在环上走，当前只累加往子树走的贡献，继续在环上走的贡献到了下一个点的时候再计算，当然还要记录继续往环上下一个点走的概率。最后要注意由于每个点不能经过两次，所以在环上走的时候不能回到自己。那么我们得到表达式
如果再走就回到原点贡献是 概率∗(down[x]+dis[x][上一个点]) 概 率 ∗ ( d o w n [ x ] + d i s [ x ] [ 上 一 个 点 ] ) $$概率*(down[x]+dis[x][上一个点])$$
否则每个点的贡献是 概率∗(son[x]∗down[x]son[x]+1+dis[x][上一个点]) 概 率 ∗ ( s o n [ x ] ∗ d o w n [ x ] s o n [ x ] + 1 + d i s [ x ] [ 上 一 个 点 ] ) $$概率*(\frac{son[x]*down[x]}{son[x]+1}+dis[x][上一个点])$$
这样处理出环上的点的 up u p $up$之后再用类似的办法求出其他点的 up u p $up$。最后用同样的式子计算答案即可。
代码细节非常多，我写了不少注释。

#include <bits/stdc++.h>
using namespace std;int n,m,fa[100010],hed[100010],cnt,inq[100010],book[100010],pd,ji,sta[100010],tp;
int cir[30];//存哪些点在环上
double down[100010],up[100010],son[100010],ans;
int hf[100010];//记录每个点在有根树上父节点的个数
double gailv,len;//记录在环上走到每个点的概率和沿着环走的长度
int vis[100010];//记录环上的点是否被访问过 
int fr[100010];
double dis[50][50];
struct node
{int to,next,from;double dis;
}a[500010];
void add(int from,int to,double dis)
{a[++cnt].to=to;a[cnt].dis=dis;a[cnt].from=from;a[cnt].next=hed[from];hed[from]=cnt;
}
void dfs(int x,int f)//找哪些点在环上（按照在环上的顺序记录）
{if(pd==1)return; for(int i=hed[x];i;i=a[i].next){int y=a[i].to;if(y!=f){if(inq[y]==1){pd=1;book[y]=1;cir[++ji]=y;while(sta[tp]!=y){           cir[++ji]=sta[tp];book[sta[tp]]=ji;--tp;}dis[book[x]][book[y]]=dis[book[y]][book[x]]=a[i].dis;for(int j=fr[x];j;j=fr[a[j].from]){int k=book[a[j].from],l=book[a[j].to];dis[k][l]=dis[l][k]=a[j].dis;}return;}sta[++tp]=y;inq[y]=1;fr[y]=i;dfs(y,x);inq[y]=0;--tp;fr[y]=0;}       }
}
void getf(int x)//无根树转有根树
{for(int i=hed[x];i;i=a[i].next){int y=a[i].to;      if(y!=fa[x]&&!book[y]){++son[x];fa[y]=x;hf[y]=1;            getf(y);}}
}
void dfs1(int x)//处理down
{for(int i=hed[x];i;i=a[i].next){int y=a[i].to;if(y!=fa[x]&&son[x]&&!book[y]){dfs1(y);down[x]+=(down[y]+a[i].dis)/son[x];}}
}
void dfs2(int x)//处理up
{for(int i=hed[x];i;i=a[i].next){int y=a[i].to;if(y!=fa[x]&&(!book[y])){   if(son[x]+hf[x]-1)up[y]=a[i].dis+(son[x]*down[x]-down[y]-a[i].dis+up[x]*hf[x])/(son[x]+hf[x]-1);      else if(son[x]==1)up[y]=a[i].dis+(son[x]*down[x]-down[y]-a[i].dis+up[x]);dfs2(y);}}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;++i){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}if(m==n)//基环树{sta[++tp]=1;inq[1]=1;dfs(1,0);//找哪些点在环上for(int i=1;i<=ji;++i){getf(cir[i]);hf[cir[i]]=2;dfs1(cir[i]);           }       for(int i=1;i<=ji;++i) {gailv=0.5;//往环上编号大和编号小的方向走的概率都是0.5 int x=i+1,last=i;if(x>ji)x=1;while(x!=i)//往编号大的方向走{if((x%ji+1)==i)//不能走回原点up[cir[i]]+=gailv*(down[cir[x]]+dis[last][x]);elseup[cir[i]]+=gailv*(son[cir[x]]*down[cir[x]]/(son[cir[x]]+1)+dis[last][x]);               gailv/=(son[cir[x]]+1);last=x;++x;if(x>ji)x=1;}gailv=0.5;x=i-1;last=i;if(x==0)x=ji;while(x!=i)//往编号小的方向走{int nxt=x;--nxt;if(nxt==0)nxt=ji;if(nxt==i)//不能走回原点up[cir[i]]+=gailv*(down[cir[x]]+dis[last][x]);elseup[cir[i]]+=gailv*(son[cir[x]]*down[cir[x]]/(son[cir[x]]+1)+dis[last][x]);gailv/=(son[cir[x]]+1);last=x;--x;if(x==0)x=ji;}}for(int i=1;i<=ji;++i)dfs2(cir[i]);       for(int i=1;i<=n;++i)ans+=(down[i]*son[i]+up[i]*hf[i])/(son[i]+hf[i]);ans/=n;}else//树{getf(1);dfs1(1);        dfs2(1);for(int i=1;i<=n;++i)ans+=(down[i]*son[i]+up[i])/(son[i]+hf[i]);ans/=n;}printf("%.5lf\n",ans);return 0;
}