题解 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)。

此部分代码：

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 是环的大小。

此部分代码：

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);
    }
}