题解 P2081 【[NOI2012]迷失游乐园】

发现这张图要么是一棵树，要么是一棵基环树。 我们先考虑树的做法。设一个点 $i$ 的度数是 $deg_i$。 考虑二次扫描与换根法。我们设$f_i$表示以 $1$ 为根时，以 $i$ 为根的子树中一条从 $i$ 出发的依照题面描述的路径的期望长度。 这种定义自然也能做。但是，为了方便（也是为了与接下来基环树部分的讲解一致），我们统一将 $f_i$ 乘以（以 $1$ 为根时 $i$ 节点的儿子数），即 $deg_i-[i\neq1]$。 于是，我们现在有转移方程： $$f_x=\sum\limits_{y\in son_x}\dfrac{f_y}{\max(1,deg_y-1)}+e(x,y)$$ 其中，$e(x,y)$ 是连接 $x,y$ 的边的长度。而那个除数与 $1$ 取 $\max$，是因为如果不这么干在 $y$ 是叶子时就会出现除数为零，尽管此时 $f_y$ 也等于 $0$。 则我们经历过一遍DP后，$f_1$ 的值已经是期望长度了（只不过要除以一个 $deg_1$）。我们现在考虑二次扫描更新所有的 $f_y$。 我们有 $$f_y'=f_y+\dfrac{f_x-\Big(\dfrac{f_y}{\max(1,deg_y-1)}+e(x,y)\Big)}{\max(1,deg_x-1)}+e(x,y)$$ 其中，最外面的那个大分数的分子，是删去 $y$ 影响后的 $f_x$；而此时以 $y$ 为根时，$x$有 $deg_x-1$ 个儿子，故也要除掉才能得到真实的期望长度。最终得到的 $f_y'$，即为真实的 $f_y$。 最终答案为 $$\dfrac{\sum\limits_{i=1}^n\dfrac{f_i}{deg_i}}{n}$$ 其中 $\sum$ 内的是每个位置的期望长度；因为不确定起始位置，故最终要除以 $n$。 时间复杂度 $O(n)$。 此部分代码： ```cpp namespace SUB1{ double f[100100],res; void dfs1(int x,int fa){ for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa)dfs1(edge[i].to,x),f[x]+=f[edge[i].to]/max(1,deg[edge[i].to]-1)+edge[i].val; } void dfs2(int x,int fa){ for(int i=head[x],y;i!=-1;i=edge[i].next)if((y=edge[i].to)!=fa)f[y]+=(f[x]-f[y]/max(1,deg[y]-1)-edge[i].val)/max(1,deg[x]-1)+edge[i].val,dfs2(y,x); } void solve(){ dfs1(1,0); dfs2(1,0); for(int i=1;i<=n;i++)res+=f[i]/deg[i]; printf("%lf\n",res/n); exit(0); } } ``` 接下来我们再考虑基环树的情形。 我们考虑找出在环上的节点。然后，以环上每个节点为根，在它所对应的子树内，仍然一次搜索DP出 $f_i$。 接下来我们考虑对于环上的节点，求出它真实的答案。 我们设当前考虑的是节点 $i$。此时，我们发现以它为起点的路径，只有两种情况： 1. 向 $i$ 节点方向的子树中延伸。此时即为 $f_i$。 2. 向 $i$ 节点的子树外延伸。此时，它可以经过环上与 $i$ 节点相邻的两条边中任意一条边，且最多只能经过一条边。故我们可以分别断开两条边中的某一条，并求出此时的结果，最终加在一起即可。 我们设 $h_j$ 表示断开其中一条边后，以 $i$ 为根时，以 $j$ 为根的子树中一条从 $j$ 出发的依照题面描述的路径的期望长度。显然，对于非环上的点，我们有 $h_j=f_j$；故我们只需考虑环上节点即可。 则我们对于环上节点 $x$，有 $$h_x=f_x+\dfrac{h_y}{\max(1,deg_y-1)}+e(x,y)$$ 其中，$y$ 是 $x$ 节点在环上与其相邻的点。 需要注意的是，当这个 DP 在环上绕了一圈后，是不能重新回到 $i$ 点的——毕竟这条边已经断掉了嘛。所以，我们有两个特例： 1. 当 $x$ 的下一个节点是 $i$ 时，我们直接有 $h_x=f_x$； 2. 当 $x$ 的下一个节点就是（1）中所述节点时，因为它不能走向 $i$，所以我们有 $$h_x=f_x+\dfrac{h_y}{\max(1,deg_y-2)}+e(x,y)$$ 其它情形的 $h_x$ 即为前文所述递推式求得。 我们令 $g_x$ 表示一个节点的最终答案，则当一整圈全部DP完后，我们就有 $g_i=h_i$。（注意这里的 $h_i$ 应该包括分别断开两条边时的结果） 我们分别以环上每个节点为 $i$，都能得出它的 $g_i$；接着，我们就按照树的情形时的做法，二次扫描一下即可得出全部的 $g_x$。 时间复杂度 $O(nk)$，其中 $k$ 是环的大小。 此部分代码： ```cpp namespace SUB2{ double f[100100],g[100100],h[100100],res; int fa[100100],sz; bool on[100100]; void dfscir(int x){ for(int i=head[x];i!=-1;i=edge[i].next){ if(edge[i].to==fa[x])continue; if(!fa[edge[i].to])fa[edge[i].to]=x,dfscir(edge[i].to); else{ int y=x; while(y!=edge[i].to)on[y]=true,y=fa[y],sz++; on[y]=true,sz++; } if(sz)break; } } void dfsord(int x){ for(int i=head[x];i!=-1;i=edge[i].next)if(!on[edge[i].to]&&edge[i].to!=fa[x])fa[edge[i].to]=x,dfsord(edge[i].to); } void dfs1(int x){ for(int i=head[x];i!=-1;i=edge[i].next)if(!on[edge[i].to]&&edge[i].to!=fa[x])dfs1(edge[i].to),f[x]+=f[edge[i].to]/max(1,deg[edge[i].to]-1)+edge[i].val; } void dfsg(int x,int fr,int rem){ h[x]=f[x]; if(rem==1)return; for(int i=head[x];i!=-1;i=edge[i].next)if(on[edge[i].to]&&edge[i].to!=fr){ dfsg(edge[i].to,x,rem-1); h[x]+=h[edge[i].to]/max(1,deg[edge[i].to]-1-(rem==2))+edge[i].val; } } void dfss(int x){ for(int i=head[x];i!=-1;i=edge[i].next)if(!on[edge[i].to]&&edge[i].to!=fa[x]){ g[edge[i].to]=(g[x]-f[edge[i].to]/max(1,deg[edge[i].to]-1)-edge[i].val)/max(1,deg[x]-1)+edge[i].val; g[edge[i].to]+=f[edge[i].to]; dfss(edge[i].to); } } void solve(){ fa[1]=-1,dfscir(1); for(int i=1;i<=n;i++)if(on[i])fa[i]=0,dfsord(i); // for(int i=1;i<=n;i++)printf("%d ",fa[i]);puts(""); for(int i=1;i<=n;i++)if(on[i])dfs1(i); // for(int i=1;i<=n;i++)printf("%lf\n",f[i]);puts(""); for(int i=1;i<=n;i++)if(on[i])dfsg(i,0,sz),g[i]=h[i]; for(int i=1;i<=n;i++)if(on[i])dfss(i); for(int i=1;i<=n;i++)res+=g[i]/deg[i]; printf("%lf\n",res/n); } } ```