点这里看题目。

分析

好美妙的思维题目！反正我是做不来了。

显然我们可以对于每一个点计算它作为根的答案，这个答案又可以通过 DP 的方式求出来。

它难道还能不是个 DP ?

直接求解概率比较复杂，而操作序列的总方案数比较好求，是 ((n-1)!) 。不过，由于同一个操作序列的成功概率会因为每条边的操作而不同，因此我们实际上 DP 的不应该是方案数，而是所有操作序列的成功概率的和。最后将答案再除以 ((n-1)!) 。

设 (P(p)) 为操作序列 (p) 成功概率。 DP 的东西可以理解为：

第一眼不难想到这样一个状态：

(f(u,i))：以 (u) 为根的子树内，剩余的边有 (i) 条，最后操作到只有一个 (u) 的概率和。

然后发现，如果仅仅局限性地要求根必须保留，就会忽略那些 " 先随意合并，再让根节点过来吞掉 " 的情况。

因此，我们可以对状态加上一些限制：

(f(u,i))：以 (u) 为根的子树内，剩余的边有 (i) 条，且当前的 (u) 标号已经变成了根的，继续操作留下根的概率和。

这样起始状态就是 (f(u,0)=1) ，目标状态就是 (f(x,n-1)) （假设我们计算 (x) 为根的情况）。

顺便再规定一下 (s_u) 为 (u) 的子树大小。

首先我们考虑一个比较简单的情况——一棵树 (u) ，有 (x) 条剩余边；另一棵树 (v) ，有 (y) 条剩余边。现在我们要把它们 " 粘 " 起来。这就意味着边的数量不会变。

根据定义，我们实际上是考虑序列概率和的变化。也就自然分成两个部分：

(mathcal{1.})序列贡献的变化。因为序列的成功概率是可以合并的，所以我们可以得到新的贡献为 (f(u,x) imes f(v,y)) 。

(mathcal{2.})序列形态的变化。考虑未操作边，合并的方案是 (inom{x+y}{x}) ；已操作边，合并的方案是 (inom{s_u-x+s_v-y-2}{s_u-x-1}) 。两种边的顺序不可调换，因而一种组合序列对应的方案数是 (inom{x+y}{x} imes inom{s_u-x+s_v-y-2}{s_u-x-1}) 。

可以发现，每种新序列的新形态的方案都相同，因而有新贡献为 (f(u,x) imes f(v,y) imes inom{x+y}{x} imes inom{s_u-x+s_v-y-2}{s_u-x-1}) 。

再考虑节点 (u) 的转移。我们尝试合并上来 (v) 。我们只需要想办法把 ((u,v)) 合并到 (f(v)) 的操作序列中，得到新的贡献 (g(v)) （ (g(v,i)) 表示合并过后有 (i) 条剩余边的概率和 ），就可以套用之前的计算方法合并 (u) 和 (v) 了。

不妨枚举一下我们需要的 (g(v,i)) ，再枚举一下 (f(v,j)) ，考虑 (f(v,j)) 对 (g(v,i)) 的贡献。

(mathcal{1.} j>i) ，显然这种情况下 (f(v,j)) 不可能贡献到 (g(v,i))。

(mathcal{2.} j<i) ，考虑此时的合法合并：首先，当 (v) 的子树内剩余 (i-1) 条边的时候， (u) 被替换为了根；接着， (v) 继续合并直到剩余 (j) 条边；然后， ((u,v)) 合并并且保留 (u) 的标号；最后进入到 (f(v,j)) 。注意到 (u) 必须保留，因此贡献为 (frac 1 2f(v,j)) 。

(mathcal{3.} j=i) ，这意味着 (g(v,i)) 要操作的边就是 (f(v,j)) ，那么 ((u,v)) 就应该随着 (v) 子树中那些被删除的边一起删除。显然那些边总共有 (s_v-1-j) 条，对应就有 (s_v-j) 个空位。注意到 (u) 并不一定要保留，因此贡献就是 ((s_v-j)f(v,j)) 。

所以我们可以首先处理出来 (g(v)) ，然后按照上述方法进行合并，就可以得到 (f(x,n-1)) ，除以 ((n-1)!) 就得到了答案。

可以发现这个转移本质上类似于树形背包，因此单次时间应该是 (O(n^2)) 。总时间就是 (O(n^3)) 。

有价值的点：

(mathcal{1.}) DP 的状态设计，有一定的难度。

(mathcal{2.}) DP 的转移，也有一定的难度。

没错，这道题就是一道 DP 毒瘤思维题。

代码

#include <cstdio>

typedef long long LL;

const int MAXN = 55;

template<typename _T>
void read( _T &x )
{
	x = 0;char s = getchar();int f = 1;
	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
	x *= f;
}

template<typename _T>
void write( _T x )
{
	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
	if( 9 < x ){ write( x / 10 ); }
	putchar( x % 10 + '0' );
}

struct edge
{
	int to, nxt;
}Graph[MAXN << 1];

double fac[MAXN];
double f[MAXN][MAXN], g[MAXN], tmp[MAXN];
int head[MAXN], siz[MAXN];
int N, cnt;

void addEdge( const int from, const int to )
{
	Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
	head[from] = cnt;
}

void init()
{
	fac[0] = 1;
	for( int i = 1 ; i <= N ; i ++ )
		fac[i] = fac[i - 1] * i;
}

double C( const int n, const int m ) { return fac[n] / fac[m] / fac[n - m]; }

void DFS( const int u, const int fa )
{
	siz[u] = 1;
	f[u][0] = 1; for( int i = 1 ; i <= N ; i ++ ) f[u][i] = 0;
	for( int i = head[u], v ; i ; i = Graph[i].nxt )
		if( ( v = Graph[i].to ) ^ fa )
		{
			DFS( v, u );
			for( int k = 0 ; k <= N ; k ++ ) tmp[k] = g[k] = 0;
			for( int k = 0 ; k <= siz[v] ; k ++ )
				for( int j = 0 ; j <= k ; j ++ )
				{
					if( k == j ) g[k] += ( siz[v] - k ) * f[v][j];
					else g[k] += 0.5 * f[v][j];
				}
			for( int j = 0 ; j < siz[u] ; j ++ )
				for( int k = 0 ; k <= siz[v] ; k ++ )
					tmp[j + k] += f[u][j] * g[k] * C( j + k, j ) * C( siz[u] - j - 1 + siz[v] - k, siz[v] - k );
			siz[u] += siz[v];
			for( int k = 0 ; k < siz[u] ; k ++ ) f[u][k] = tmp[k];
		}
}

int main()
{
	read( N );
	for( int i = 1, a, b ; i < N ; i ++ )
		read( a ), read( b ), addEdge( a, b ), addEdge( b, a );
	init();
	for( int i = 1 ; i <= N ; i ++ ) 
	{
		DFS( i, 0 );
		printf( "%.10lf
", f[i][N - 1] / fac[N - 1] );
	}
	return 0;
}