CF1060F

· · 题解

这个题我看到的所有题解状态定义的解释感觉都有问题。。

对于每个点分别计算概率。以要算的这个点为根。

设 f(x,i) 表示 x 子树内，最后删去的 i 条边满足，删去这些边之后，子树的根的编号是删去这 i 条边之前根的编号的概率。我们要求 f(rt,n-1)。

为什么要这么设？因为 (u,v) 这条边删之前，v 子树内的边可以随便删，删之后要求不能影响到 u。于是有这个状态设计。

1. 加入边 $(x,y)$，枚举 $(x,y)$ 在从后往前第 $i$ 步被删掉，设这时转移到的新 dp 数组为 $g_j$。 - $i\le j$，也即 $(x,y)$ 删的时候（这里 $x,y$ 已经不一定是原来的那两个点了，但地位是等价的），必须选择 $x$ 保留。在这条边之后删的 $i-1$ 条边都需要选择保留 $y$（因为 $y$ 已经合到 $x$ 上，所以就是选择 $x$）概率为 $0.5f(y,i-1)$。 - $i>j$，则 $(x,y)$ 无论选择谁都不会影响，只需要最后 $j$ 轮符合要求即满足状态定义，故概率为 $f(y,j)$。 2. 接着，考虑合并根相同的两个子树 $(x\to y,x\to z)$。这两个子树状态第二维定义是相同的，所以 $f(y,i),f(z,j)$ 合并时 $i,j$ 这一坨边、$sz_y-1-i,sz_z-1-j$ 这一坨边分别合并，两者之间有明确顺序。合并时的概率，是 $0^x1^y,2^z3^w$ 归并，最终满足 $0,2$ 都在 $1,3$ 前的概率。最终的方案数有 $\dbinom {x+z}x\dbinom {y+w}y$ 种，总的归并方案有 $\dbinom{x+y+z+w}{x+y}$ 种，应该乘上 $\dfrac{\dbinom {x+z}x\dbinom {y+w}y}{\dbinom{x+y+z+w}{x+y}}$。 第一步是 $O(n^4)$ 的，第二步是 $O(n^3)$ 的。总时间复杂度 $O(n^4)$（前缀和一下就 $O(n^3)$ 了）。