给一棵$n$个节点的树，每次等概率选择树中剩下边的一条进行缩边，这条边的两个端点有相同的概率被保留，求最后每个点被留下的概率。
1 //minamoto 2 #include<bits/stdc++.h> 3 #define db double 4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 inline int read(){ 8 #define num ch-'0' 9 char ch;bool flag=0;int res; 10 while(!isdigit(ch=getc())) 11 (ch=='-')&&(flag=true); 12 for(res=num;isdigit(ch=getc());res=res*10+num); 13 (flag)&&(res=-res); 14 #undef num 15 return res; 16 } 17 const int N=55; 18 int n,head[N],ver[N<<1],Next[N<<1],tot; 19 inline void add(int u,int v){ 20 ver[++tot]=v,Next[tot]=head[u],head[u]=tot; 21 } 22 int sz[N];double fac[N],dp[N][N],g[N],tmp[N]; 23 inline double C(int n,int m){ 24 return fac[n]/fac[m]/fac[n-m]; 25 } 26 void dfs(int u,int fa){ 27 dp[u][0]=sz[u]=1; 28 for(int i=head[u];i;i=Next[i]){ 29 int v=ver[i];if(v==fa) continue; 30 dfs(v,u),memset(g,0,sizeof(g)); 31 for(int j=0;j<=sz[v];++j) 32 for(int k=0;k<=j;++k) 33 if(j>k) g[j]+=dp[v][k]; 34 else if(j==k) g[j]+=2*(sz[v]-j)*dp[v][k]; 35 memset(tmp,0,sizeof(tmp)); 36 for(int j=0;j<sz[u];++j) 37 for(int k=0;k<=sz[v];++k) 38 tmp[j+k]+=dp[u][j]*g[k]*C(j+k,j)*C(sz[u]-j-1+sz[v]-k,sz[u]-j-1); 39 memcpy(dp[u],tmp,sizeof(dp[u])); 40 sz[u]+=sz[v]; 41 } 42 } 43 int main(){ 44 // freopen("testdata.in","r",stdin); 45 n=read(),fac[0]=1; 46 for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i*2; 47 for(int i=1,u,v;i<n;++i) 48 u=read(),v=read(),add(u,v),add(v,u); 49 for(int i=1;i<=n;++i){ 50 memset(dp,0,sizeof(dp)); 51 dfs(i,0); 52 printf("%.10lf ",dp[i][n-1]/fac[n-1]); 53 } 54 return 0; 55 }