CF1060F Shrinking Tree

题面传送门

考虑枚举最后剩下的点，然后令它为根。

对于每个不是根的点，我们记 \(ti_i\) 表示 \(i\) 是什么时候和它的父亲合并的，\(op_i\) 表示 \(i\) 在和父亲合并的时候是不是和一号点合并的。

我们考虑对 \(ti\) 和 \(op\) 两个数组计数，最后除以 \(2^{n-1}(n-1)!\) 就是最后剩下这个点的概率。

\(ti\) 显然如果是一个排列就合法，关键是 \(op\) 。观察发现，如果一个点 \(x\) 的祖先合并的时间均早于 \(x\)，那么 \(op_x=1\) ，反之 \(op_x=0\)。对于每个 \(op_x=0\)，都会使排列的答案乘上 \(2\)。

考虑设 \(dp_{i,j}\) 表示 \(i\) 子树内的答案已经确定，要求祖先的删除时间不能早于当前子树内第 \(j\)个 的方案数。特别的，如果 \(j\) 大于 \(i\) 子树大小，则对祖先的时间没有限制。

考虑合并这两个类似背包的东西。枚举限制最终在什么位置，就可以用组合数计数，单次dp复杂度\(O(n^3)\)。

然后考虑加上当前节点，当前节点显然要小于限制的位置。然后先钦定这个点的 \(op_x=0\)，然后减去 \(op_x=1\) 的方案数，就可以做到当 \(op_x=0\) 的时候对排列数乘 \(2\) 了。

总时间复杂度 \(O(n^4)\)，当然可以前缀和优化到 \(O(n^3)\)，但是我懒。

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=50+5,M=5e6+5,K=5e4,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(263082);
int n,m,k,x,y,z,Si[N];vector<int> S[N];lb dp[N][N],g[N],C[N][N];
void DP(int x,int La){
 	dp[x][1]=1;Si[x]=0;for(int i:S[x]) if(i^La){
		DP(i,x);Mc(g,dp[x]);Me(dp[x],0);
		for(int j=1;j<=Si[x]+1;j++){
			for(int h=1;h<=Si[i]+1;h++){
				if(j==Si[x]+1&&h==Si[i]+1){ dp[x][Si[x]+Si[i]+1]+=g[j]*dp[i][h]*C[Si[x]+Si[i]][Si[i]];continue;}
				if(j<=Si[x]) for(int p=j;p<=j+h-1;p++) dp[x][p]+=g[j]*dp[i][h]*C[p-1][j-1]*C[Si[x]+Si[i]-p][Si[x]-j];
				if(h<=Si[i]) for(int p=h;p<=j+h-1;p++) dp[x][p]+=g[j]*dp[i][h]*C[p-1][h-1]*C[Si[x]+Si[i]-p][Si[i]-h];
			}
		}
		Si[x]+=Si[i];
	}
	if(La){
		Mc(g,dp[x]);Me(dp[x],0);
		for(int i=1;i<=Si[x]+1;i++) for(int j=1;j<=i;j++) dp[x][i+1]+=g[i]*2,dp[x][j]-=g[i];
		Si[x]++;
	}
}
int main(){
	freopen("1.in","r",stdin);
	int i,j;scanf("%d",&n);for(i=1;i<n;i++) scanf("%d%d",&x,&y),S[x].PB(y),S[y].PB(x);
	for(i=0;i<=n;i++) for(C[i][0]=j=1;j<=i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
	for(i=1;i<=n;i++){
		Me(dp,0),DP(i,0);
		lb Ans=0;for(j=1;j<=n;j++) Ans+=dp[i][j];
		for(j=1;j<n;j++) Ans/=2*j;printf("%.10Lf\n",Ans);
	} 
}