题解 CF1060F 【Shrinking Tree】

shadowice1984 · 2018-10-23 11:37:05 · 题解

dp好题啊……

其实这题强行浮点数输出有点炸精度……

不过只要你和std错的一样的话卡精度什么的根本不存在

题意已经比较清楚了这里我们就不再赘述

本题题解

我们发现n的范围相当小只有50,这样的话我们似乎可以依次枚举每一个点,然后计算这个点在最终的点中出现的概率

那么我们可以O(N!)的枚举每一种删边的排列,之后对于每一种排列求出点i存活的概率,将这些概率加在一起最后除一个(n-1)!就行了

那么此时我们需要做相当重要的一步转化，否则我们无法理解接下来的转移方程是怎么一回事

这个做法基于这样的一个简单的原理,假设枚举到的点是i,我们仅仅保证每一个i最后存活下来的概率被计算一次，至于不合法的方案我们并不管他到底是怎么不合法了

我们做这样一个简单的转化

我们将合并一个边变成删除一个边的操作

然后接下来进行分情况讨论,如果这条边(u,v)连接的点都不是i点,那么假设删去这条边之后v和i变得不再联通我们就直接将v的标号改为i

否则我们以50%的概率从u,v中选择一个点x并将这两个点的标号都改成x同时删除u,v这条边

这样转化之后，如果最后所有点的标号全部为i的话我们认为点i成功存活了否则点i就不是最后的点

那么这样做的依据何在呢？

我们发现一个重要的事实是在每一个i存活下来的方案当中，如果i存活下来了，他必然在每一个合并操作当中都"顶替"了和他合并的另一个节点，那么这个操作就等价于把另一个点的编号也赋成i这个操作

注意这个操作在i被别的点顶替的时候操作就会变得不等价了，因为此时所有标号为i的点在原来的图上是一个点，我们应该更改所有标号为i的点的标号而不是仅仅更改一个点的标号

不过这种情况下既然i已经gg了我们为什么要管这种情况呢？

另一个情况是当我们合并一条和i相连的边时另一个点v已经是好几个点合并之后的结果了,此时我们似乎也会碰到刚才那种修改多个点的标号的情况,然而事实是我们仅仅考虑i成功存活的情况,既然被合并的点早晚都要变成i,并且它变不变成i仅仅和吸收它的点变不变成i有关，我们不如一开始就把这个点赋成i好了

所以这就是为什么我们无脑的把其中一个点赋成i的原因了，因为我们不考虑非法情况而仅仅考虑合法情况，在所有点都要变成i这个大前提下我们所作的转化就是等价的

那么根据这个我们就可以设计一个树形dp了,为了方便起见我们以i为根进行树形dp，这样树中的所有点都在i的子树里了

那么此时我们可以很显然的得出合并之后的状态应该是dp(u,p+q),根据我们状态的定义,所有点变成i的概率就是dp(u,p)dp(v,q)但是由于我们状态是枚举所有删边的排列然后再把每种排列对应的概率相加的计算方式,因此我们还需要考虑新生成的排列数目

显然我们之后剩下的边可以任意混合之前删掉的边也可以任意混合,所以我们乘上两个系数{p+q \choose p}和{siz_{u}+siz_{v}-1-p-q \choose siz_{v}-q}就行了

所以我们合并的转移方程就是

接下来让我们考虑加一条父亲边的转移

那么我们假如要计算dp(u,k)的话我们先枚举一下这剩下的k条边当中包不包含父亲边,假如不包含父亲边的话那么u这个子树就和fa的标号毫无关系(因为当fa的标号变成i之前u和fa之间的边就被割掉了,然后u的标号就被强制赋值成i了)

所以满足不包含父亲边的限制条件的方案数就是dp(u,k)(siz_{u}-k)了

如果剩下的k条边当中包含父亲边的话，我们就枚举父亲边断开的时候这k条边中还剩下几条边,由于此时断开的时候i这个标号有1/2的标号会消失,所以要乘上一个0.5的系数

所以我们的转移方程就是

然后我们就可以愉快的dp了~

边界条件是dp(u,0)=1

最后提取答案的时候是dp(i,n-1)的值

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=60;typedef long double ld;
int n;ld fac[N];ld dp[N][N];ld tr[N];
int v[2*N];int x[2*N];int ct;int al[N];int siz[N];
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline ld c(int n,int m){return fac[n]/fac[m]/fac[n-m];}
inline void dfs(int u,int f)
{
    siz[u]=1;dp[u][0]=1;
    for(int i=al[u];i;i=x[i])
    {
        if(v[i]==f)continue;dfs(v[i],u);
        for(int j=0;j<siz[u]+siz[v[i]];j++)tr[j]=0;int tot=siz[u]+siz[v[i]]-1;
        for(int p=0;p<siz[u];p++)
            for(int q=0;q<=siz[v[i]];q++)
                tr[p+q]+=dp[u][p]*dp[v[i]][q]*c(p+q,p)*c(tot-p-q,siz[v[i]]-q);
        siz[u]+=siz[v[i]];for(int j=0;j<siz[u];j++)dp[u][j]=tr[j];
    //  printf("dfs %d\n",u);
    //  for(int j=0;j<=siz[u];j++)printf("%lf ",(double)dp[u][j]);printf("\n");
    }
    if(f!=0)
    {
        for(int i=0;i<=siz[u];i++)tr[i]=0;
        for(int i=0;i<siz[u];i++)
        {
            tr[i]+=(siz[u]-i)*dp[u][i];
            for(int j=i+1;j<=siz[u];j++)tr[j]+=dp[u][i]*0.5;
        }
        for(int i=0;i<=siz[u];i++)dp[u][i]=tr[i];
    }return;
}
int main()
{
    fac[0]=1;for(int i=1;i<=50;i++)fac[i]=fac[i-1]*i;
    scanf("%d",&n);
    for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u);
    for(int i=1;i<=n;i++)
    {dfs(i,0);printf("%.10lf\n",(double)dp[i][n-1]/(double)fac[n-1]);}return 0;
}