CF1060F Shrinking Tree

考虑分别以每个点为根计算概率，可以计算所有边固定了收缩顺序的概率之和后除以 \((n-1)!\) 即为答案

设 \(f_{x,i}\) 表示在 \(x\) 的子树内，删除最后 \(i\) 条边前后根的编号不发生变化的概率和，所求即为 \(f_{rt,n-1}\)

记当前点为 \(v\)，父节点为 \(u\)，因为收缩 \((u,v)\) 时，之前的编号是随意的，之后相当于 \(v\) 变成了 \(u\)，后面剩下的边就不能将 \(v\) 删除掉，所以这样设计状态

考虑从 \(f_v \to f_u\)

首先需要在 \(f_v\) 的基础上添加 \((u,v)\)，转移到 \(g_j\)，但是表示是 \(v\) 子树内的边和 \((u,v)\) 中删除最后 \(j\) 条边前后父节点代表的根不发生变化的概率，枚举 \((u,v)\) 是从后向前第 \(i\) 条边删除的，若 \(i \le j\)，首先需要保留 \(u\)，而且后面的边已经与 \(u\) 相连（可看作 \(v\) 变成了 \(u\)），所以后面的 \(i-1\) 条边也是让它被保留的，那么贡献为 \(\frac{f_{v,i-1}}{2}\)，否则是不会对 \(j\) 之内的直接产生影响，只需要确保后来没被覆盖即可，所以贡献为 \(f_{y,j}\)

再考虑合并所有的 \(v\)，相当于是将 \(u\)，\(v\) 的后面确定的 \(j\) 条边合并起来和前面的合并起来分别的方案的乘积，所以贡献是 \(f_{u,i}f_{v,j}\tbinom{i+j}{j}\tbinom{siz_u +siz_v-i-j}{siz_v-j}\)

#include<bits/stdc++.h>
using namespace std;
int n,x,y,siz[51];
double fac=1,f[51][51],g[51],h[51],c[101][101];
vector <int> G[51];
void dfs(int x,int u){
	siz[x]=1,f[x][0]=1;
	for(int y:G[x]){
		if(y==u) continue;
		dfs(y,x);
		memset(g,0,sizeof(g));
		for(int i=1;i<=siz[y];i++){
			for(int j=0;j<=siz[y];j++){
				if(i<=j) g[j]+=f[y][i-1]/2;
				else g[j]+=f[y][j];
			}
		}
		for(int i=0;i<siz[x];i++) for(int j=0;j<=siz[y];j++) h[i+j]+=f[x][i]*g[j]*c[i+j][j]*c[siz[x]+siz[y]-1-i-j][siz[y]-j];
		siz[x]+=siz[y];
		for(int i=0;i<siz[x];i++) f[x][i]=h[i],h[i]=0;
	}
}
int main(){
    scanf("%d",&n);
	for(int i=1;i<n;i++) fac*=i;
	for(int i=0;i<=n*2;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1];
	}
	for(int i=2;i<=n;i++){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		memset(f,0,sizeof(f));
		dfs(i,0);
		printf("%.10lf\n",f[i][n-1]/fac);
	}
	return 0;
}