Link:

Solution:

原来CF的官方题解也能鸽啊……

该题思路：

1、对于每个点删边方案数为$fac[n-1]$，总贡献为每种方案下满足的概率的和，接下来直接求贡献

2、每次将该点看成根，树形$dp$，设$dp[i][j]$表示根到$i$该子树还有$j$条边的贡献

3、考虑合并子树（算上根到子树的边），由于两边互不影响，相乘后再乘上删边顺序不同的组合数皆可

$dp[v1][i]*dp[v2][j]*C(i+j,i)*C((sz[v1]-1-i)+(sz[v2]-1-j),sz[v1]-1-i)$

4、考虑用子树答案$dp[i]$算出加上子树根到其父亲的边后$cur[j]$的答案

$j>i$时为了不重复计算，变数只有最后$u,v$的合并，产生的贡献为$0.5*dp[i]$

$j=i$时考虑$u,v$合并和$sz[v]-1-i$条边的删除顺序任意，产生贡献为$(sz[v]-i)*dp[i]$

Code:

#include 
     
      using namespace std;#define X first#define Y second#define pb push_backtypedef double db;typedef long long ll;typedef pair
      
        P;const int MAXN=55;struct edge{
   int nxt,to;}e[MAXN<<2];int n,x,y,head[MAXN],sz[MAXN],tot;db cur[MAXN],tmp[MAXN],dp[MAXN][MAXN],fac[MAXN];void add(int x,int y){e[++tot]=(edge){head[x],y};head[x]=tot;}db C(int x,int y){
    return fac[x]/(fac[x-y]*fac[y]);}db solve(int x,int y){
    return C(x+y,x);}void dfs(int x,int anc){    sz[x]=1;dp[x][0]=1;    for(int i=head[x];i;i=e[i].nxt)        if(e[i].to!=anc)        {            dfs(e[i].to,x);            memset(cur,0,sizeof(cur));            memset(tmp,0,sizeof(tmp));            for(int j=0;j<=sz[e[i].to];j++)            {                for(int k=0;k