CF1060F Shrinking Tree

布满荆棘的人生 2022-01-06 16:09 475阅读 0赞

[http://codeforces.com/problemset/problem/1060/F][http_codeforces.com_problemset_problem_1060_F]

### 题解 ###

仙题。

参考：[https://www.cnblogs.com/Mr-Spade/p/9747399.html][https_www.cnblogs.com_Mr-Spade_p_9747399.html]

首先我们可以枚举每个点作为最后保留的节点，以它作为根节点进行树形\\(dp\\)。

注意到我们删去一条边可以看做把边权弄成0，这样根节点可以在边权为0的边上随意走动。

我们设计一个状态：\\(dp\[u\]\[i\]\\)表示在以\\(u\\)为根的子树中，当根节点走到\\(u\\)时，子树内还剩下\\(i\\)条边的方案数。

这样相当于倒着推，那么最后的答案就是根节点刚进入这棵树的状态，就是\\(dp\[rot\]\[n-1\]\\)。

那么我们接下来要考虑子树的\\(dp\\)值合并。

我们枚举了两个状态\\(dp\[u\]\[i\]\\)和\\(dp\[v\]\[j\]\\)。

我们发现这样不太够，我们还需要知道从\\(u\\)走到\\(v\\)的时候还有多少条边，我们令它为\\(k\\)。

然后我们考虑概率是多少。

首先这个\\(k\\)肯定不能大于\\(j\\)。

当\\(k=j\\)时，说明\\(u-v\\)这条边在\\(u\\)来之前就已经被干掉了，那么这条边的删除时间我们可以在\\(v\\)子树里的任意一条边的删除时间中插入，并且这条边的删除对根是没有影响的，所以就是\\((size\[v\]-j)\*1\\)。

当\\(k<j\\)时，相当于是先到\\(u\\)，然后\\(v\\)中的一些边被删除了，然后再去删除\\(u-v\\)，这时需要考虑概率了，只有一半的概率会被选中，所以系数是\\(0.5\\)。

最后我们再考虑方案数。

当前两颗子树还剩下\\(i\\)和\\(j\\)条边，这两组边删去是互不影响的，所以这样的方案数就是插板法，注意已经删去的\\(size\[u\]-i-1\\)条边和\\(size\[v\]-j\\)也是互不影响的，也要用插板法算一下。

### 代码 ###

#include<bits/stdc++.h>
    #define N 52
    #define mm make_pair
    using namespace std;
    typedef long double ll;
    int head[N],tot,size[N],n;
    ll c[N][N],dp[N][N],tmp[N],g[N];
    inline int rd(){
        int x=0;char c=getchar();bool f=0;
        while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
        while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
        return f?-x:x;
    }
    struct edge{
        int n,to;
    }e[N<<1];
    inline ll calc(int n,int m){return c[n][m];}
    inline ll path(int n,int m){return c[n+m][n];}
    inline void add(int u,int v){
        e[++tot].n=head[u];e[tot].to=v;head[u]=tot;
    }
    void dfs(int u,int fa){
      dp[u][0]=1;size[u]=1;
      for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){
        int v=e[i].to;
        dfs(v,u);
        for(int i=0;i<=size[v];++i){
            g[i]=0;
            for(int j=0;j<i;++j)g[i]+=0.5*dp[v][j];
            g[i]+=(size[v]-i)*dp[v][i];
        } 
        for(int j=0;j<size[u];++j)
            for(int k=0;k<=size[v];++k)
                tmp[j+k]+=dp[u][j]*g[k]*path(j,k)*path(size[u]-1-j,size[v]-k);
        for(int j=0;j<=size[u]+size[v];++j)dp[u][j]=tmp[j],tmp[j]=0;
        size[u]+=size[v];
      }
    }
    int main(){
        n=rd();
        for(int i=0;i<=n;++i){
            c[i][0]=1;
            for(int j=1;j<=i;++j)c[i][j]=c[i-1][j-1]+c[i-1][j];
        }
        int u,v;
        for(int i=1;i<n;++i){
            u=rd();v=rd();
            add(u,v);add(v,u);
        }
        ll xx=1;
        for(int i=1;i<n;++i)xx=xx*i;
        for(int i=1;i<=n;++i){
          memset(dp,0,sizeof(dp));
          dfs(i,0);
          double x=dp[i][n-1]/xx;
          printf("%.10lf\n",x);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/ZH-comld/p/11037894.html

[http_codeforces.com_problemset_problem_1060_F]: http://codeforces.com/problemset/problem/1060/F
[https_www.cnblogs.com_Mr-Spade_p_9747399.html]: https://www.cnblogs.com/Mr-Spade/p/9747399.html