Codeforces 1060 F. Shrinking Tree

一道思维好题啊...感觉这种类型的题很检验基本功是否扎实（像我这样的就挂了）。

题意：你有一棵 $n$ 个点的树，每次随机选择一条边，将这条边的两个端点合并，并随机继承两个点标号中的一个，问对于每一个点来说，最终剩下的那个点标号等于它的标号的概率。 $n \leq 50$ ，用浮点数方式输出。

碰到浮点数输出的题就很怕卡精，不过这道题似乎不卡，担心卡精可以开 $l o n g d o u b l e$ （还要吐槽一句cf的 $C + + 11$ 对 $l o n g d o u b l e$ 的输出好像不是很资瓷...还要转 $d o u b l e$ 输出）。

好了现在开始讲做法吧。我们的大体思想是每一个点分别求解答案。对于每一个点，用某种方法算出它最终被留下的方案数，那么再除以 $(n - 1)!$ 显然就是答案。不过要注意的一点是因为标号的继承是随机的，因此对于同一种删边顺序，得到的结果可能不同，因此我们算出的其实是所有顺序下这个点保留的概率的总和（可能是浮点数），但是为了接下来表达的简便，不妨不严谨的称其为方案数。

现在来关心怎么求出每一个点被留下的方案数，我们将要求答案的点 $x$ 当作树的根，并用 $s i z e_{i}$ 表示以 $i$ 为根的子树的大小。考虑树形 $d p$ ，我们用 $f_{i, j}$ 表示当根节点的标号继承到 $i$ 点时，如果 $i$ 的子树还剩下 $j$ 条边，根节点的标号最终被保留下来的方案数。那么 $f_{x, n - 1}$ 就是我们想要的答案。

我们先来解决一个小问题：

假设我们将当前节点 $u$ 的子树划分为两部分，并且已经知道了左半部分还剩 $i$ 条边时的方案数 $a$ 和右半部分还剩 $j$ 条边时的方案数 $b$ ，如何求解它们对整棵子树还剩 $i + j$ 条边的方案数的贡献？

显然左右两部分的子树对对方是没有影响的，因此我们可以将左右的方案合并。只要剩下的左边的 $i$ 条边和右边的 $j$ 条边在之后删除的相对顺序不变，那么一定会得到同一种结果，因此这部分合并的方案数就是 $(\binom{i + j}{i})$ 种（即在删除序列的 $i + j$ 个空位种选 $i$ 个给左边的边）。

同时我们还要注意已经删除的边，在真实的操作序列中它们也同样需要合在一起。因此和上面相似，我们假设左边原来一共有 $x$ 条边，右边原来一共有 $y$ 条边，那么这部分合并的方案数就是 $(\binom{x + y - i - j}{x - i})$ 。

综上所述，它们的贡献应该是 $a * b * (\binom{i + j}{i}) * (\binom{x + y - i - j}{x - i})$ 。

那么沿着刚刚的想法继续思考，我们或许可以采取如下策略 $d p$ ：对于某一棵以 $u$ 为根的子树，不考虑任何子树时有 $f_{u, 0} = 1$ 。假如我们有一种方法，可以计算出一个单点在只考虑一棵子树时的答案，那么我们的问题就做完了，因为我们在新考虑一棵子树的时候，我们可以先计算只考虑它时的答案而将其视为我们刚刚所讲的“右半部分”，将之前已经计算完的部分视为“左半部分”，就可以直接按照之前所讲的方法合并。

现在我们只要解决如何计算只考虑 $u$ 的某一棵子树时的答案，设其根为 $v$ 。显然我们可以枚举 $i$ ，表示我们想要求其还剩下 $i$ 条边时的答案，设其为 $g_{i}$ ，接着再枚举 $j$ ，考虑 $f_{v, j}$ 对 $g_{i}$ 的贡献。分三类情况讨论：

$1$ 、假设 $j < i$ ，显然合法的过程应该是这样的： $v$ 的子树中合并到还剩 $i - 1$ 条边时，根的标号继承到了 $u$ 上，接着 $v$ 的子树中的边继续合并到只剩 $j$ 条边，接着根的标号再从 $u$ 继承到了 $v$ 上。注意到 $u$ 的标号继承到 $v$ 上发生的概率是 $\frac{1}{2}$ ，因此此时 $f_{v, j}$ 对 $g_{i}$ 的贡献是 $\frac{1}{2} f_{v, j}$ 。

$2$ 、假设 $j = i$ ，显然合法的过程应该是这样的： $v$ 的子树原来共有 $s i z e_{v} - 1$ 条边，如果要剩下 $i$ 条边，应该删除 $s i z e_{v} - 1 - i$ 条边，而 $u$ 到 $v$ 的连边也应该随着这些边的删除一起被删除，考虑被删除的 $s i z e_{v} - 1 - i$ 条边组成的序列， $u$ 到 $v$ 的连边可以插入到 $s i z e_{v} - i$ 个空位（因为两端也是可以的）中的任何一个。同时我们可以发现如此一来，当根节点的标号继承到 $u$ 时， $u$ 和 $v$ 的连边已经消失，因此就不需要考虑那 $\frac{1}{2}$ 的概率了，贡献是 $(s i z e_{v} - i) * f_{v, j}$ 。

$3$ 、假设 $j > i$ ，画图考虑一下就发现这是没有合法方案的，贡献是 $0$ 。

于是我们终于完成了最后一块拼图，得到了可行的解法。最后总结一下做法，我们分别计算每一个答案，接着进行树形 $d p$ 。对于每一个新考虑的儿子，我们先计算只考虑这个子树的情况，接着将其与原有答案进行合并。计算一下复杂度，在每一个点更新它对父亲的贡献时似乎至多是 $O (n^{2})$ 的，但是考虑合并两个大小为 $x$ 和 $y$ 的子树，代价可以做到 $O (x * y)$ ，这等价于两个子树之间的点对数。因此一次dp的复杂度应该是总点对数即 $O (n^{2})$ ，因此总复杂度是 $O (n^{3})$ 的。不过代码里我偷了个懒写了 $O (n^{4})$ 的做法，反正 $n \leq 50$ 因此也是不要紧的。

我的代码：

#include<cstdio>
#include<vector>
using std::vector;
typedef long double ldb;
const int N=55;
int n;
vector<int> G[N];
int size[N];
ldb fact[N];
ldb dp[N][N],tmp[N],g[N];
inline ldb choose(int n,int m)
{
	return fact[n]/(fact[m]*fact[n-m]);
}
void dfs(int now,int father)
{
	register int i,j;
	dp[now][0]=1;size[now]=1;
	for(auto x:G[now])
	{
		if(x==father)
			continue;
		dfs(x,now);
		for(i=0;i<=size[x];i++)
		{
			g[i]=0;
			for(j=1;j<=size[x];j++)
				if(j<=i)
					g[i]+=0.5*dp[x][j-1];
				else
					g[i]+=dp[x][i];
		}
		for(i=0;i<size[now]+size[x];i++)
			tmp[i]=0;
		for(i=0;i<size[now];i++)
			for(j=0;j<=size[x];j++)
				tmp[i+j]+=dp[now][i]*g[j]*choose(i+j,i)*choose(size[now]-1-i+size[x]-j,size[now]-1-i);
		for(i=0;i<size[now]+size[x];i++)
			dp[now][i]=tmp[i];
		size[now]+=size[x];
	}
	return;
}
signed main()
{
	int x,y;
	register int i;
	scanf("%d",&n);
	fact[0]=1;
	for(i=1;i<=n-1;i++)
		fact[i]=fact[i-1]*i;
	for(i=1;i<=n-1;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(i=1;i<=n;i++)
	{
		dfs(i,0);
		printf("%.9lf\n",(double)(dp[i][n-1]/fact[n-1]));
	}
	return 0;
}