题解 CF1060F 【Shrinking Tree】

一个比较难以理解的dp神题。 首先我们可以考虑**每次随机缩一条边**等效于**有一个长度为$n-1$的边的操作序列**，那么我们可以用序列计数的角度去处理这个东西，每个操作序列的边都有一半的概率选择一个端点，那对于我们钦定的一个点$rt$，在一个操作序列中它会有一定概率最后保留，那么我们可以求出所有操作序列这个点被保留的概率和，最后除个$(n-1)!$即可。 现在我们干脆把$rt$这个点提成根做一遍树形dp。但是这个dp如何入手呢？我们不妨假设（或者说叫钦定）一种状态就是考虑$u$这个点，$rt$现在已经克服重重困难来到了$u$点，但是$rt$怎么来的$u$点我们并不关心，**我们仅关心$u$子树内的所有边的序列**，因为我们可以使用诸如组合数之类的方式来合并两个操作序列。那么我们的大体思路应该是$dp[u]$为当$rt$这个编号转移到$u$点并将其取代之后，$u$这棵子树缩成一个$rt$编号的大点的操作序列的方案数（或者说是概率）。 我们考虑这个$dp$有没有什么值得转移的地方。我们知道$u$这个操作序列是它儿子的操作序列加上连向儿子的边**混合**而成的。那么我们不妨这样转移：  当合并过来一个儿子$v$的边的序列的时候，应该是这个儿子子树的边序列+这条连向儿子的边，所以，我们不妨在每个儿子处单独处理把这条父亲边插到自己的边序列中得到的边序列$g$，这样我们在父亲$u$处就考虑所有儿子$g$序列的合并就行了。 考虑$(u,v)$啥时候加入$v$的边序列，可以分两种情况： ①：$rt$已经移动至$u$，那么现在$u$就相当于$rt$，那么合并$(u,v)$这条边的时候必须有$\frac 1 2$的概率不让$rt$死掉，除此之外我们给$(u,v)$随便插个位置就好了。 ②：$rt$还未移动至$u$，那么我合并$(u,v)$这条边最终编号是啥并没有关系，但是，我们现在的问题是必须保证给$(u,v)$插入一个位置的时候$rt$还没有移动至$u$。 那么现在我们就需要改一下$dp$状态了，我们设$dp[u][i]$为**仅考虑$u$子树里的边序列**，当$rt$移动到$u$的时候边序列还有最后$i$条没有合并的边序列的概率和。然后对于那个对儿子扩充的$g$序列我们设$g[v][i]$为**仅考虑$v$子树和它父亲边的边序列**，当$rt$移动到它的父亲$u$时这个序列还剩下最后$i$条没有合并的边序列的概率和。 这样的话，我们重新来看一下上面两个情况： ①：显然对于一个$g[v][i]$，$(u,v)$要插到末尾$i$个位置中去，那枚举$(u,v)$之后有多少条边，然后合并完$(u,v)$就相当于$rt$移动到了$v$上，就归纳到了$v$本身的边序列，所以$g[v][i]=\frac 1 2\sum_{j=0}^{i-1}dp[v][j]$。 ②：对于$g[v][i]$这个序列来说我们只需把$(u,v)$插到前$size[v]-i$个已经合并的位置就行了，所以$g[v][i]=(size[v]-i)dp[v][i]$。 那么现在我们把每个儿子的$g$序列搞出来了，如何合并呢？其实，我们并不用考虑那么多，可以发现，儿子的边序列其实是互不影响的，因为在合并$(u,v)$的时候我们已经通过讨论避免了$rt$死掉，而每个儿子迟早会有一个点遇到$rt$，所以我们可以独立的合并儿子的$g$序列，只要我们保证在$rt$移动到$u$这个点的时刻（这是个最关键的时刻）之前已经合并了的边都在前面，之后没合并的边都在后面，就是这样：  那么我们考虑两个儿子$x,y$的合并，就是： $g[x][i]g[y][j]C_{size[x]-i+size[y]-j}^{size[x]-i}C_{i+j}^i\to dp[u][i+j]$ 前面的$C$是在这个时刻之前已经合并完的边序列混合起来，后面的$C$是在这个时刻之后的。 然后就$O(n^4)$了，还有要相信$double$，不太大的数据范围它还是能够处理阶乘组合数之类的…… 上代码~ ```cpp #include <iostream> #include <cstdio> #include <cstring> using namespace std; namespace ywy { double dp[55][55], g[55], jc[55]; inline double cnm(int n, int m) { if (n < m) return (0); return ((jc[n] / jc[m]) / jc[n - m]); } typedef struct _b { int dest; int nxt; } bian; bian memchi[1000001]; int gn = 1, heads[55]; inline void add(int s, int t) { memchi[gn].dest = t; memchi[gn].nxt = heads[s]; heads[s] = gn; gn++; } int size[55]; double h[55]; void dfs(int pt, int baba) { size[pt] = 1; dp[pt][0] = 1; for (register int i = heads[pt]; i; i = memchi[i].nxt) { if (memchi[i].dest == baba) continue; dfs(memchi[i].dest, pt); for (register int j = 0; j <= size[memchi[i].dest]; j++) { g[j] = 0; for (register int k = 0; k < j; k++) g[j] += 0.5 * dp[memchi[i].dest][k]; g[j] += (size[memchi[i].dest] - j) * dp[memchi[i].dest][j]; } for (register int j = 0; j <= size[pt] + size[memchi[i].dest]; j++) h[j] = 0; for (register int j = 0; j < size[pt]; j++) { for (register int k = 0; k <= size[memchi[i].dest]; k++) { h[j + k] += dp[pt][j] * g[k] * cnm(size[pt] - 1 - j + size[memchi[i].dest] - k, size[pt] - 1 - j) * cnm(j + k, j); } } size[pt] += size[memchi[i].dest]; for (register int j = 0; j < size[pt]; j++) dp[pt][j] = h[j]; } } void ywymain() { int n; cin >> n; jc[0] = 1; for (register int i = 1; i <= n; i++) jc[i] = jc[i - 1] * i; for (register int i = 1; i < n; i++) { int s, t; cin >> s >> t; add(s, t); add(t, s); } for (register int i = 1; i <= n; i++) { memset(dp, 0, sizeof(dp)); dfs(i, 0); printf("%.10lf\n", dp[i][n - 1] / jc[n - 1]); } } } int main() { ywy::ywymain(); return (0); } ```